June 4: Homework and exam solutions have been removed in case we want to reuse any problems in future semesters.
May 17: Exams have been graded, and final grades have been posted to eLearning and submitted to Orion. The final exam you all took is also available for future reference. Thank you all again for a tough but hopefully fulfilling semester. And best of luck to all of you taking the QE!
May 14: Grades for Midterm 2 are now available on eLearning. The mean score was a 31.7 out of 40, and the standard deviation was 5.1. If Kyle were assign grades based purely on this midterm, he would set the lower bound for a B- around 21, for a B around 24, for a B+ around 28, for an A- around 31, and for an A around 35.
Obviously, your Final Exam will be graded much more quickly.
May 12: By request, the whole notebook of scribbles from this semester's office hours is now available. The last few pages cover problems from the Spring 2019 final exam.
As a reminder, the Final Exam will be made available on eLearning Thursday, May 13th at 6:00am CDT. The exam instructions are available on the course website now in case you would like to look over them before you start the eLearning exam. Be sure to submit by Friday, May 14 at 5:59am CDT.
Good luck on the exam!
May 11: Homework 5 solutions are now available.
May 10: Sorry about the late notice, but Kyle will hold a review session tomorrow, Tuesday, May 11th from 1:00pm–2:15pm. Feel free to ask any questions you'd like in preparation for the Final Exam. The session will be recorded and uploaded to Microsoft Stream.
The Final Exam will be made available on eLearning Thursday, May 13th at 6:00am CST. The eLearning exam consists of a single "question" which links to the pdf containing all exam problems (there will likely be six or seven problems total). You should upload all of your solutions as your response to this eLearning question. You'll have three hours to submit your solutions once you start the exam. You must also submit by Friday, May 14 at 5:59am CST regardless of when you start the exam. Do not hesitate to email Kyle if you have any questions, and good luck on the exam!
Finally, Kyle apologizes for still grading Midterm 2. Even a minor illness can put a big dent in one's schedule.
May 5: Midterm 2 solutions are now available. Grades should be available this week.
May 4: A practice QE exam is available on eLearning. Please email Kyle if you do not have access to the file. As a reminder, we will not have class on Tuesday, May 5th, so you have time to take the practice QE.
April 23: Apologies for releasing it so soon after Midterm 2, but the semester ends in only two weeks. Homework 5 is now available. Is it due Saturday, May 8th on eLearning. In case you would like to typeset your solutions using LaTeX, you may find the source files useful.
April 21: Homework 4 solutions are now available.
The recording for the Midterm 2 review session is now available in the Locally Recorded Lectures tab of our Team's Lectures channel. Handwritten notes from the session are available as well.
Midterm 2 will be made available on eLearning Thursday, April 22nd at 6:00am CST. The eLearning exam consists of a single "question" which links to the pdf containing all four exam problems. You should upload all of your solutions as your response to this eLearning question. The exam instructions are available on the course website now in case you would like to look over them before you start the eLearning exam. As stated in the instructions, you'll have two hours to submit your solutions once you start the exam. You must also submit by Friday, April 23rd at 5:59am CST regardless of when you start the exam. Please be aware that this deadline is four hours earlier than the one given for Midterm 1, because eLearning is not expected to go down for maintenance this time. Do not hesitate to email Kyle if you have any questions, and good luck on the exam!
April 8: Homework 3 solutions are now available.
Also, Midterm 2 will take place Thursday, April 22nd. It will primarily cover Lectures 8 through 17 (February 25th through April 6th) on subjects like greedy algorithms, graph algorithms through all-pairs shortest paths, and dynamic programming on trees and DAGs.
As before, the exam questions will be given as a pdf on eLearning. The exam will be written as if it had a 1 hour 15 minute time limit, but you will be given 2 hours to read, write your solutions, and upload a scanned copy of your solutions to eLearning. Each student may take the exam within any 2 hour block they'd like between 6am CST on April 22nd and 5:59am CST on April 23rd. Similar to before, it would be best to take the exam between 9am CST and 3:30pm CST on the 22nd so Kyle can more quickly respond to questions about the exam problems or technical issues with uploading solutions.
April 4: Homework 4 is now available. Is it due Sunday, April 18th on eLearning. In case you would like to typeset your solutions using LaTeX, you may find the source files useful.
In addition, grades for Midterm 1 are now available on eLearning. The mean score was a 31.1 out of 40, and the standard deviation was 5.5. If Kyle were assign grades based purely on the midterm and these statistics, he would set the lower bound for a B- around 20, for a B around 23, for a B+ around 27, for an A- around 31, and for an A around 34. He apologizes for his tardiness in posting your grades.
March 30: Homework 3 and its source files have been updated to provide clarification on Problem 1 and fix an error in the figure caption for Problem 2.
March 20: Homework 3 is now available. Is it due Sunday, April 4th on eLearning. In case you would like to typeset your solutions using LaTeX, you may find the source files useful.
March 18: We hope you are enjoying your Spring Break! Midterm 1 solutions are now available. Please wait a little while longer for Kyle to grade them. Homework 3 will be released very early next week, and you'll be given the normal two weeks to complete it.
March 10: Homework 2 solutions are now available.
The recording for the Midterm 1 review session is now available in the Locally Recorded Lectures tab of our Team's Lectures channel. Handwritten notes from the session are available as well.
Midterm 1 will be made available on eLearning Thursday, March 11th at 6:00am CST. The eLearning exam consists of a single "question" which links to the pdf containing all four exam problems. You should upload all of your solutions as your response to this eLearning question. The exam instructions are available on the course website now in case you would like to look over them before you start the eLearning exam. As stated in the instructions, you'll have two hours to submit your solutions once you start the exam. You must also submit by Friday, March 12th at 9:59am CST regardless of when you start the exam. Please be aware that eLearning may be down for maintenance between 1:00am and 5:00am CST the morning of Friday, March 12th. This maintenance period is why we are delaying the end of the originally planned exam period by a few hours. Do not hesitate to email Kyle if you have any questions, and good luck on the exam!
March 5: We have uploaded a short "exam" to eLearning to make sure your setup is sound before you attempt to take the real Midterm 1 next Thursday. From 12:00am CST on Saturday, March 6th to 11:59pm CST on Monday, March 8th, you will be able to "take" this exam on eLearning. Once you start the exam, you will have seven hours to upload your solutions. Please read the instructions given on eLearning before hitting begin so you know what to expect. If during this exercise, you discover you have difficulty submitting an exam, please do not hesitate to email Kyle so we can work through the issues.
March 1: Midterm 1 will take place Thursday, March 11th. It will cover the first eight lectures (through February 23rd) on subjects like describing algorithms, run time analysis, solving recurrences, and designing divide-and-conquer and dynamic programming algorithms.
The exam questions will be given as a pdf on eLearning. The exam will be written as if it had a 1 hour 15 minute time limit, but you will be given 2 hours to read, write your solutions, and upload a scanned copy of your solutions to eLearning. Each student may take the exam within any 2 hour block they'd like between 6am CST on March 11th and 5:59am CST on March 12th. That said, it would be best to take the exam between 9am CST and 4pm CST on the 11th so Kyle can more quickly respond to questions about the exam problems or technical issues with uploading solutions.
Some time this coming week, we will ask everybody to take a short "technical practice exam" that only asks to you write and upload two pages to make sure your technology is working properly before taking the real exam.
February 21: Homework 2 is now available. Is it due Sunday, March 7th on eLearning. In case you would like to typeset your solutions using LaTeX, you may find the source files useful.
Texas guidelines say we must make up for at least one of the classes that we missed, and Midterm 1 is still tentatively schedule for March 11th (the official announcement will come later this week). Here's the plan: On Tuesday, March 9th (the Tuesday after Homework 2 is due), Kyle will hold an extra office hour from 2:30pm to 3:30pm to answer questions relevant to the midterm. Wednesday, March 10th from 10:30am to 11:45am, we'll hold an extra live lecture instead of normal office hours. We'll treat this lecture purely as a review session where you can ask Kyle any questions you have about the first two homework assignments, about things you saw in class, or even about additional problems from the text you would like to better understand before the midterm. Kyle will share recordings of the lecture as quickly as he can so you can watch before the midterm the next day.
Sorry it's been so long since we've met, but the weather outside looks great finally, and we're looking forward to seeing you all later this week!
February 18: Homework 1 solutions are now available. Please keep in mind that these are in some sense the "ideal" solutions to these problems, and they contain extra exposition and details to help further your understanding. In particular, our official solutions will generally contain more details than would be necessary for students to receive full credit.
February 17: The university will remained closed through Friday, February 19th, so we're going to cancel Kyle's office hours and the live lecture for this week. We still plan to release Homework 2 this Friday.
It looks like the weather will be much nicer next week, and we're looking forward to meeting with all of you again. In the meantime, please keep safe and warm!
February 15: Due to dangerous weather and rolling blackouts, the university has canceled all in-person and virtual activities, and it has asked non-essential employees not to work Monday or Tuesday. Therefore, we are canceling Greg's office hours for Monday, February 15th and lecture for Tuesday, February 16th.
Fortunately, there is some slack built into the schedule, so there is still time to cover all the 6363 learning objectives and prepare students for the QE using only live lectures. Unfortunately, the second homework and first midterm cover material we meant to teach last Thursday and this week, and there's a decent chance lecture will be canceled this Thursday as well.
Here is the current plan: Homework 2 will be released this Friday, February 19th whether or not we meet this week and be made due two weeks later. It will contain one or two problems that will be made easier by the next lecture or two, but you should have technically seen everything necessarily to succeed. The tentative dates for both midterms have been pushed back by a bit. See the schedule on the course webpage. We'll likely announce the final date for Midterm 1 next Thursday.
Please don't hesitate to send Kyle an email if you have any questions or concerns about the course schedule.
February 11: Due to inclement weather, the university has canceled all in-person and virtual activities, including today's lecture. We would rather meet with you live than post a video recorded without student participation, so today's scheduled lecture material will be presented next Tuesday. If class is canceled next Tuesday as well, then we may have to post an asynchronous lecture or two after all.
Kyle will show up for today's office hours, because they're more of an informal/optional thing anyway. Please send an email if you were planning to attend office hours but cannot safely do so thanks to the weather. Maybe we can schedule another time to chat.
Homework 1 is still due tomorrow, February 12th. We are still trying to decide how to handle scheduling for future homework and the midterms, because you might benefit from seeing the next lecture before starting Homework 2. We'll keep you updated on any decisions we make.
February 2: We have a TA! Gregory Van Buskirk will assist the class in holding office hours and grading homework. His office hours will run from 12pm to 2pm every Monday on MS Teams.
Speaking of office hours, you are all highly encouraged to attend office hours with both Kyle and Greg. You can ask any questions you'd like about the homework or lectures, including getting help with the homework problems. You can even ask about problems in the texts if you'd like extra practice. We hope to see you there!
January 29: Homework 1 is now available. Is it due Friday, February 12th on eLearning. In case you would like to typeset your solutions using LaTeX, you may find the source files or solutions template useful.
January 19: The first set of lecture notes have been posted to the schedule below. Also, the first locally recorded lecture has been uploaded to MS Stream. You can access it through the "Locally Recorded Lectures" tab on the "Lectures" channel in the "CS 6363.003 2212" team. Please continue to check for notes and recordings regularly. I won't do future announcements about them to avoiding overwhelming your inboxes.
Also, if you still don't have access to the MS Team, and you haven't done so already, please send an email to let me know.
January 18: Hello all, and welcome to CS/SE 6363.003.21S — Design and Analysis of Computer Algorithms. I'm Kyle, an assistant professor at UTD and your instructor for the course.
This section of the course is intended for students planning to take the Algorithms QE. While I won't assume prior knowledge beyond the prerequesites common to all sections of CS 6363, I do want you to gain skills in designing and analyzing algorithms beyond a baseline understanding of the process. You'll likely find things more difficult relative to other CS 6363 sections, especially with the homework.
This course will have regular lectures presented by myself and office hours where we can discuss class topics or homework problems. I plan to do live lectures and office hours through MS Teams, under the "CS 6363.003 2212" team. I will also post recorded lectures there in case you can't attend in person, and we can use it as a discussion space if you'd like. If you have a strong preference for a different platform, please let me know, but we may not be able to change much due to the size of the class. I find eLearning in particular to be very frustrating to use, so I'd prefer to keep as much off of eLearning as possible, all things being equal.
This course has a website at https://personal.utdallas.edu/~kyle.fox/courses/cs6363.003.21s/. I will post copies of every announcement and homework assignment on the website. The website will also contain the only copy of the (always changing) course schedule along with links to relevant readings and lecture notes I use for myself as a script. I keep old class websites around forever in case you want to read up on algorithms topics that I've taught before. The website is also the best resource for understanding course policies and getting general writing advice.
We'll also use eLearning as the way I email announcements to everybody, the place to submit homework and do exams, and the place I put your grades.
I'm looking forward to a great semester with you all, and I'll see most of you this Tuesday, January 19th at 1pm in the Live Lectures meeting of MS Teams.
The schedule below will be updated with new subjects and recommended readings throughout the semester. Exact topics discussed in each lecture may change.
Shortly before or after each lecture, I will update the readings with my own notes/script. Use at your own risk! My notes likely have typos or maybe even a few bugs!
Date | Subject/Event | Reading | Notes |
---|---|---|---|
Tue, Jan. 19th | Administrivia, "What is an algorithm?", designing and describing algorithms | Erickson 0; CLRS 2–2.2; lecture notes; scribbles | |
Thur, Jan. 21st | Reductions, induction, recursion | Erickson I (through Section 2 plus however many examples you think would be helpful), Erickson 1–1.2; lecture notes; scribbles | |
Tue, Jan. 26th | Divide-and-conquer, mergesort, quicksort | Erickson 1.4–1.6; CLRS 2.3, 4.0, 4.3, 7–7.1; lecture notes; scribbles | |
Thur, Jan. 28th | Asymptotic notation, solving divide-and-conquer running time recurrences | Erickson 1.7, 1.9; CLRS 3, 4.4–4.5; typeset notes on asymptotic notation from CS 4349; lecture notes; scribbles | |
Tue, Feb. 2nd | Quicksort analysis, element selection | Erickson 1.5, 1.8; CLRS 7–7.2, 7.4.1, 9.0, 9.3; lecture notes; scribbles | |
Thur, Feb. 4th | Closest pair of points in the plane, Karatsuba multiplication | Suri; CLRS 33.4; lecture notes; scribbles (recommended) | |
Tue, Feb. 9th | Dynamic programming, Fibonacci numbers, rod cutting | Erickson 2.4–2.5, 3.1, 3.3–3.5; CLRS 15–15.1, 15.3; lecture notes; scribbles | |
Thur, Feb. 11th | No class; university closed due to inclement weather | Homework 1 due Friday, February 12th (source) (solutions template) (solutions) | |
Tue, Feb. 16th | No class; university closed due to inclement weather | ||
Thur, Feb. 18th | No class; university closed due to inclement weather | ||
Tue, Feb. 23rd | Edit distance, longest increasing subsequence(?) | Erickson 2.6, 3.6–3.7; CLRS 15.4; lecture notes; scribbles | |
Thur, Feb. 25th | Optimal binary search trees, maximum independent set in trees | Erickson 3.9–3.10; CLRS 15.5; lecture notes; scribbles | |
Tue, Mar. 2nd | Maximum independent set in trees, greedy algorithms, class scheduling | Erickson 3.10, 4.2–4.3; CLRS 16–16.2; lecture notes; scribbles | |
Thur, Mar. 4th | Huffman codes | Erickson 4.4; CLRS 16.3; lecture notes; scribbles | Homework 2 due Sunday, March 7th (source) (solutions) |
Tue, Mar. 9th | Graph basics review, breadth-first search, depth-first search | Erickson 5–5.6, 6–6.2; CLRS 22–22.3; lecture notes; scribbles | |
Wed, Mar. 10th, 10:30am–11:45am | Review session for Midterm 1 | Please prepare your own questions concerning the first two homework assignments, class material, or other problems from the texts. Handwritten scribbles are available as well. | |
Thur, Mar. 11th | Midterm Exam 1 (solutions) | ||
Tue, Mar. 16th | No class; university closed for Spring break | ||
Thur, Mar. 18th | No class; university closed for Spring break | ||
Tue, Mar. 23rd | Depth-first search, topological sort, dynamic programming on DAGs | Erickson 6–6.4; CLRS 22.3–22.4 (CLRS 24.2 for shortest paths in DAGs); lecture notes; scribbles | |
Thur, Mar. 25th | Minimum spanning trees, Kruskal's algorithm, the Prim-Jarník algorithm, Bor˚uvka's algorithm | Erickson 7; CLRS 23; lecture notes; scribbles | |
Tue, Mar. 30th | Single source shortest paths, Bellman-Ford | Erickson 8–8.3, 8.7; CLRS 24–24.1, 24.5; lecture notes; scribbles | |
Thur, Apr. 1st | Dijkstra's algorithm, BFS redux, shortest paths in DAGs | Erickson 8.4–8.6; CLRS 24.2–24.3; lecture notes; scribbles | Homework 3 due Sunday, April 4th (source) (solutions) |
Tue, Apr. 6th | All-pairs shortest paths, Johnson's algorithm, dynamic programming | Erickson 9–9.2, 9.5, 9.8; CLRS 25, 25.2–25.3; lecture notes; scribbles | |
Thur, Apr. 8th | Maximum flows and minimum cuts | Erickson 10–10.4; CLRS 26—26.2; lecture notes; scribbles | |
Tue, Apr. 13th | Ford-Fulkerson augmenting paths, flow decompositions, Edmonds-Karp maximum flow algorithms, recent results | Erickson 10.5—10.7; CLRS 26.2; lecture notes; scribbles | |
Thur, Apr. 15th | Applications of maximum flows, edge/vertex disjoint paths, maximum bipartite matching, other assignment problems | Erickson 11; CLRS 26.3; lecture notes; scribbles | Homework 4 due Sunday, April 18th (source) (solutions) |
Tue, Apr. 19th | NP-hardness, CircuitSAT, SAT | Erickson 12.1–12.5; CLRS 34–34.4; lecture notes; scribbles | |
Wed, Apr. 21st, 10:15am–11:30am | Review session for Midterm 2 | Handwritten scribbles are available. | |
Thur, Apr. 22nd | Midterm Exam 2 (solutions) | ||
Tue, Apr. 27th | More NP-hardness proofs, 3SAT, MaxIndSet, the general pattern | Erickson 12.6–12.9; CLRS 34.4–34.5.2; lecture notes; scribbles | |
Thur, Apr. 29th | Even more NP-hardness proofs, MaxClique, VertexCover, 3Color, Hamiltonian cycle, SubsetSum | Erickson 12.9–12.14; CLRS 34.5.2–34.5.5; lecture notes | |
Thur, May 6th | Practice QE review | Handwritten scribbles are available. | Homework 5 due Saturday, May 8th (source) (solutions) |
Tue, May 11th, 1:00pm–2:15pm | Review session for Final Exam | Handwritten scribbles are available. All scribbled notes from this semester's office hours are available. | |
Thur, May 13th | Final Exam |