CS 146: Data Structures and Algorithms, Spring 2019

Cay S. Horstmann | Department of Computer Science | San Jose State University | MH416

Date Topics covered on that date Homework assigned on that date
(due next class, unless otherwise specified)
January 24 Taylor Jan 28 Introductions, Course Management, Start Finding Maximum.
  1. For those trying to add: submit your information to this google form by early morning Tuesday, January 29.
  2. Submit proof of prerequisites on Canvas.
  3. Submit the Homework Statement on Canvas.
  4. Please sign up for the class piazza discussion list. Upload a photo, preferably one of you.
  5. Watch the Lists, Stacks, and Queues Playlist. This should be review, except the 4th video, which you can skip if you want. Generally, don't try to get ahead of the class for videos. They will be most effective if watched when assigned. The whole playlist is 40-50 minutes (depending on if you watch the 4th video), and because it is review, it should be fairly easy to follow.
  6. Take Lists quiz in Canvas after the videos.
  7. Skim: Appendix A.1, especially equations A.1, A.2, A.5, A.6, A.7.
  8. Read/Skim (somewhere in between?): Appendix A.2.
  9. Written Homework 1
  10. Watch and understand Introduction to Heaps at https://youtu.be/WCm3TqScBM8 .
  11. Read 6.1-6.2 if anything was unclear in the video.
  12. Take the Heap Basics Canvas quiz.
  13. Bring computers to class from now on, ready to run Java and Eclipse.
January 29 Taylor Jan 30 Homework,
Finish max, 2nd max,
Timing of ArrayLists vs LinkedLists Experiment code
  1. Read/skim B.4, B.5 as needed.
  2. Written homework 2: Do B.4-1, B.4-3, B.4-4, B.5-1, B.5-4 (tricky one).
  3. Watch Binary Heaps for Priority Queues video at https://youtu.be/-WEku8ZnynU and/or read 6.5.
  4. If you like, you can also watch the Linear Time BuildHeap and HeapSort videos and/or read 6.3/6.4, but it's not required (yet).
  5. Read through Heap Program Submission. Ignore everything about Web-CAT for now. Do the first part of the coding assignment—the insert method. For now, add
    @Ignore("Test is ignored until February 1")
    before the second unit test in SimpleGivenTests. Bring your solution to class on Thursday. You must have run the unit test. Hopefully, it has passed. If not, tell me on Thursday what failed and what you plan to do about it.

    Important: If you run into problems with your programming homework that prevent you from completing it, you must ask on Piazza by Wed. night, or you will fail code review.

January 31 Taylor Feb 4

In-class code review of your first homework submission. We do this early so that you can decide before the drop deadline whether this course is for you.

If you are bored, to work on while you wait: Given a heap array (that is, a heap in implicit format), and an integer k, and a value x, give an algorithm to find if there are k items larger than x in a heap. How efficient is your algorithm?

  1. Work on Heap Program Submission. Implement both the insert and changeKey method. Submit your work to Web-CAT.
  2. If you are having problems with Heap Program Submission 1 in Web-CAT, that is, the heap insertion and changeKey functionality (before worrying about the efficiency of changeKey), you need to meet me face to face during code review or my office hour on Tuesday, February 5. We absolutely need to review your programming background and determine whether you are likely to succeed in this class.
  3. After submitting your code, you need to review it with me. Submitting code without review isn't worth anything.
  4. Watch and understand Linear Time BuildHeap at https://youtu.be/MiyLo8adrWw .
  5. Read 6.3 if anything was unclear in the video.
  6. Take the Linear Time Build-Heap Canvas quiz.
  7. Watch and understand HeapSort at https://youtu.be/onlhnHpGgC4 .
  8. Read 6.4 if anything was unclear in the video.
  9. Take the HeapSort Canvas quiz.
  10. Watch Proofs (Introduction to Loop Invariants).
  11. Watch conversion to binary 1, and then take the Conversion to Binary 1 quiz in Canvas
  12. Watch conversion to binary 2, and then take the Conversion to Binary 2 quiz in Canvas.
  13. Watch Conversion to Binary Proof and take the Conversion to Binary Proof quiz.
Feb 5 Taylor Feb 6 Drop deadline. Defining Problems and Loop Invariants.
Why Use Loop Invariants?
Selection Sort and/or SearchAnalysis.
  1. Read Chapter 2
  2. Written homework 3: From text, do: 2.1-3, 2.1-4, 2.3-3 (The book's numbering system puts exercise 2.1-3 just after book section 2.1.)
  3. Look at 2.2-2. You don't need to do it, just read the question well. We may do it in class.
  4. Look at 2-2. (The book's numbering system puts 2-2 at the end of chapter 2.) You don't need to do it, just read the question well. We may do it in class.
  5. Be prepared to present an algorithm for this problem: for each value in an array, find the latest value preceding it with a smaller value.
  6. Asymptotic Notation: Definitions at https://www.youtube.com/watch?v=lRD35H39o_E .
  7. Take the Asymptotic Definitions 1 Canvas Quiz on that video.
  8. Asymptotic Notation: Proofs, Properties, and Pictures at https://www.youtube.com/watch?v=cGRHR9cSPSA .
  9. Asymptotic Notation: Runtime of Simple Programs and Loops at https://www.youtube.com/watch?v=TMJdzIVYQ1w .
  10. Asymptotic Notation: Usage at https://www.youtube.com/watch?v=pCQOIHh1kK4 .
  11. Take the Asymptotic Definitions 2 Canvas Quiz on those videos.
  12. Read 3.1 very closely
  13. Written homework 3 (cont'd): Do problems 3.1-1, 3.1-3, and 3.1-4, no more than 5 minutes each.
  14. Watch Iterated Functions and log* at https://www.youtube.com/watch?v=Z2vprYeJ0qs .
  15. Read 3.2, much less closely.
Feb 7 Taylor Feb 11 Asymptotic notation proof example
Discussion of Heap experiments
Asymptotic Notation Exercise: 3.3a from text.
  1. Read 4.0 (the part of chapter 4 before 4.1).
  2. Watch and understand: Recurrence Relations: Substitution Method at https://youtu.be/7lq-rBdM62o .
  3. Read 4.3.
  4. Take the Substitution Quiz in Canvas
  5. Written homework 4: Do 4.3-1, 4.3-2, 4.3-3, and the second half of 4.3-8.
    Note: 4.3-8 should read T(n) = 4T(n/2) + n, not +n^2. It is incorrect in the first couple of printings.
  6. Watch and understand: Recurrence Relations: Recursion Tree Method at https://youtu.be/V081HoFHJKw .
  7. Read 4.4.
  8. Take the Recursion Tree quiz in Canvas
  9. Written homework 4 (cont'd): Do 4.4-2 (Use a recursion tree to determine a good asymptotic upper bound on the recurence T(n) = T(n/2) + n^2.)
Feb 12 Taylor Feb 13 Recurrence Tree/Substitution Method Examples
Heap problem from
Start Chip Testing Problem
  1. Watch and understand my Master Theorem video at https://youtu.be/qCDZm7wGDxY . Note, the new channel has a much shorter video at https://youtu.be/AKixfFsmMus . Unfortunately, I spent so much time figuring out how to cut down on its time that I think it is nearly impossible to understand. I only point it out because it might be reasonable to use as a review later on, after you have already watched and understood the original video. Also, you might want to watch it from time 5:00-6:15.
  2. Read 4.5, skim 4.6 as needed.
  3. Take the Canvas Quiz on the Master Method Intuition.
  4. Written homework 5: Do 4-1
  5. Watch and understand CS50 Top-Down Mergesort at https://youtu.be/sWtYJv_YXbo .
  6. Watch and understand CS50 Bottom-Up Mergesort at https://youtu.be/EeQ8pwjQxTM .
  7. Take the Canvas quiz on Mergesort.
Feb 14 Taylor Feb 18 Finish Chip Problem
Using the Master Theorem
Heap Lab
Recurrence Exercise: T(n) = 2T(n/2) + n/ lg n
  1. Programming Assignment 1B is due Feb. 17.
  2. Read 7.0-7.2.
  3. Until Fall 2018, I used the CS50 Quicksort video at https://youtu.be/aQiWF4E8flQ to introduce quicksort. Unfortunately, it has been taken down, probably due to all of the violence. I do not see another video that matches the Cormen book's version. (I am leaving the link up in case they make it visible again.) https://www.youtube.com/watch?v=MZaf_9IZCrc&t=7s is a good model of Cormen's partition, until the 4:00-4:15 mark where he needlessly shifts the large partition instead of just swapping the pivot with the first large element. https://www.youtube.com/watch?v=kUon6854joI is okay, but has a completely different partition method. Same for https://www.youtube.com/watch?v=SLauY6PpjW4, which is a little different in that it doesn't leave the pivot between the partitions, but instead includes it in one of the partitions. The popular https://www.youtube.com/watch?v=ywWBy6J5gz8 has yet another partition method. None of these methods aren't ideal if there are a lot of repeated elements. The quicksort quiz will give details for simulated partitioning during quicksort.
  4. Written homework 6: Do problems 7.1-1, 7.2-1, 7.2-2, 7.2-3, 7.2-4.
  5. Take Quicksort quiz on Canvas
  6. Read 7.3.
  7. Read (don't need to do) problem 7-2 from the end of the chapter.
  8. Read 9.2
  9. Written homework 6 (cont'd): Do 9.2-4
Feb 19 Taylor Feb 20 Berlin Mergesort (top down and bottom up),
Insertion Sort: Precise Analysis
Counting Inversions
  1. Our next programming assignment will be on balanced binary(ish) trees, working towards B-Trees. You should start with the first 5 videos in the series, posted at

    1. Part 0, and take Canvas quiz.
    2. Part 1, and take Canvas quiz.
    3. Part 2, and take Canvas quiz.
    4. Part 3.
    5. Part 4, and take Canvas quiz (covers parts 3 and 4).

    There is a brief handout on the topics from the videos here. The material hasn't changed since Fall 2012, so don't worry about the date. If you like, you are also free to reference Chapters 12, parts of 13, and 18 (which will cover through the 8th video in the series, not just the 5 above). Or, go with the 8 videos and the 1.5 page handout. Your call...

  2. Start working on a 2-3 tree program. Program specifics are here. The code is officially due Tuesday, 2/26, at the start of your class section. You have your code submitted to Web-CAT before your section starts: I will look at each student's code for just a couple of minutes, to tell them what they should work on next. I won't do that if you don't have some real attempt at the code for your section. I will spend most of that class, and the next, doing this code review. (You should expect to be reviewed twice.) Spend a minimum of 3 hours working on the code before Tuesday, as well as a bit of time on a few test cases. Up to five hours might be reasonable, but don't spend more than that. If you can pass these very basic tests (without hard-coding solutions), you are in great shape. Even the first 4 tests will be helpful. At the absolute minimum, you should be passing the first test, and all tests should compile and run, even if they don't give correct answers.

    Many students, feeling completely lost, start with BinarySearchTree.java code from CS46B. (A pretty version is here.) I don't know that starting with this code is a great idea, but knowing that many students will, I am providing it just to make that path more convenient, should you choose to follow it. In the end, your code probably should not look too similar to the BST code, but both of the structures are trees, so there might be at least a bit of similarity. If you are feeling ready to tackle the world, definitely feel free (or encouraged) to ignore the BST code and start fresh on your own, you might end up with nice code more quickly. Or not.

  3. Please come to class, prepared and on time, on 2/26. This is the most difficult programming assignment of the semester, so be prepared to put in work and ask questions.

Feb 21 Taylor Feb 25 Quicksort, QuickSelect Recurrence, Analysis
  1. Watch Linear Sorts and Sorting Lower Bounds at https://www.youtube.com/watch?v=Nz1KZXbghj8 . It is a long video (52 minutes). The first 32 minutes are on lower bounds, and Counting sort is covered until 44:30, and then Radix sort after that. Quick note, at 45:20, he should say "linear" instead of "n lg n".
  2. Watch Bucket Sort. (Understand, in full, the first 13 minutes. The analysis comes after that, and the overall take-away from the analysis is that it runs in expected O(n) runtime.)
  3. Read Chapter 8 as needed to understand these videos. Compared to the book, the video version of counting sort is slightly less efficient (asymptotically the same), but easier to understand.
  4. Take the Comparison Tree Model Canvas Quiz on two above videos.
  5. Written homework 7: Do 8.1-1, 8.1-3, 8.2-1, 8.2-2, 8.3-1, 8.3-3, 8-4.1, 8.4-2
Feb 26 Taylor Feb 27 City Silhouette Exercise
Linear Sorts
Sorting Lower Bounds
23-Tree Program Lab
  1. Work on the programming assignment.
  2. BTrees Part 5
  3. BTrees Part 6
  4. BTrees Part 7
  5. Take the Canvas quiz after the last video.
Feb 28 Taylor Mar 4 SIGCSE 2-3, 2-3-4, B Tree
Memory Hierarchy
Binary Search with Unknown Bounds
City Silhouette Problem Ideas
  1. Set 75 minutes aside for this fantastic Practice Exam, directly taken from the Spring 2014 semester. Set an alarm. If you want to spend more than 75 minutes on it, change pen colors at 75 minutes so that you can easily tell what you got done in the time limit. This is your homework to turn in (Written homework 8).
Mar 5 Taylor Mar 6 City Silhouette: 4 algorithms
City Silhouette Lower Bound
Midterm review
  1. Study for the rote midterm. Here is an exam template. Find/make one sample exercise for each problem and solve it.
  2. Written homework 9: Turn in the problems that you picked to work, and your work on them.
Mar 7 Taylor Mar 11 Midterm
  1. Work on the Wrestler problem, it is problem 22.2-7. Once you know how you want to represent data, figure out what your algorithm is, and how long it will take.
  2. Review the first 1.5 pages of D.1
  3. Watch this playlist, in order.
  4. There is a Canvas Quiz for after the 2nd, 3rd, and 4th videos.
  5. Review all of B.4, and earlier parts of B if needed to understand B.4. Read 22.1-22.3. When reading, you only need to read in detail the parts you didn't already understand from the video. Basically, you can just skim until you get to something you don't already know, and then read that part closely.
  6. The following problems, from the book, should be rote (and easy) after the videos and reading. For each problem, read the problem, if you are absolutely positive that you know exactly how to correctly do the problem, that is when it is okay to skip it. If you have any question whatsoever, you should do the problem. Written homework 10: 22.1-1, 22.1-2, 22.1-3, 22.2-1, 22.2-7 (should now be easier), 22.3-1, 22.3-2, 22.3-3, 22.3-5.
Mar 12 Taylor Mar 13 Graphs: Introduction to Topological Sorting
Thought question: how do you model co-requisites with graphs?
The 23 tree code assignment will be extended 1 week.
  1. Watch this playlist, in order.
  2. Read/Skim Chapter 22.4 as needed (it covers the first and 3rd videos from the playlist). There is a canvas quiz for after the first video, and another for the 2nd and 3rd.
  3. Written homework 11: Do 22.4-1, 22.4-3, 22.4-4
  4. Read Chapter 22.5. Sorry, no video yet, Dr. Taylor recorded a first draft a while ago but it's not yet ready for prime time. Try to understand the material without a video—it can be done.
  5. Written homework 11 (cont'd): Do 22.5-1, 22.5-2, 22.5-3
Mar 14 Taylor March 18 Strongly Connected Components

Read Chapter 23.
Written homework 12: Do 23.1-1, 23.1-3, 23.1-5, 23.2-2

Mar 19 Taylor March 20 MST's, Disjoint Sets
How to Model Co-Requisites (dag.pdf)
  1. Skim 21-21.2 as needed. Read 21.3. (Optional: 21.4)
  2. Written homework 13: Do 21.3-1, 21.3-3. Please note the union tiebreaker: the first set connects to the second. The tiebreaker is not conceptually important, but will make a huge difference in the answer, and understanding, for this particular instance. (Optional: take a look at 21.3-2, if you want an idea of how recursion simplifies code nicely.)
Mar 21 Taylor March 25 Single Source Shortest Path Examples
Taylor 23 Tree code
  1. Watch this playlist, in order.
  2. Read 24-24.3 as needed after the videos.
  3. Skim (or more if you like) 24.4
  4. Written homework 14: Do 24.1-1, 24.2-1, 24.3-1 just to check your understanding
Mar 26 Taylor March 27 SSSP Review,
Counting Paths in DAGs
(intro to Dynamic Programming),
Student Chain: Zombies
  1. Read 25-25.2. Part 25.1 can be skimmed.
  2. This video, while not up to the high standards of this course, gives a walkthrough of the algorithm.
  3. Written homework 15: Do 25.2-1, 25.2-6, 25.2-7
  4. I have set two deadlines for the Job Scheduling Program: the first, due 4/11 but with code shut-off on 4/15, won't do any large scale efficiency checks (as long as it is reasonable). The second, due 4/18 with cut-off 4/22, has some big efficiency checks. Worry about the first one first.
  5. The 3rd programming assignment will be due April 11, with submission cut-off on April 15. If not for the break, I wouldn't post it quite yet, but just in case anybody wants an early start: Scheduling Program. I won't answer questions about it over the break, but I am willing to answer questions until the break.
Mar 28 Taylor April 8 Floyd Warshall Review
Zombie Aftermath
Homework 3
Dijkstra with negative weights
Non-DFS topological sort algorthm
  1. Work on your program.
  2. Practice Midterm 2! Put aside 75 minutes for it. Turn it in—Written homework 16.
  3. Have a great break.
Apr 9 Taylor April 10 Dynamic Programming:
Fibonacci Sequence
Rod Splitting (Chapter 15.1 in 3rd edition)
  1. Review 15.1 as needed.
  2. Written homework 17: Do Exercises 15.1-2, 15.1-3, and 15.1-4.
Apr 11 Taylor April 15 2nd Rote Exam Preview
  1. Review 15.4 as needed.
  2. Written homework 18: Do Exercises 15.4-2, 15.4-4
Apr 16 2nd Rote Exam Review
  • Study for the rote midterm. Here is an exam template. Find/make one sample exercise for each problem and solve it.
  • Written homework 19: Turn in the problems that you picked to work, and your work on them.
Apr 18 2nd Rote Exam Recover from 2nd Rote Exam
Apr 23 Taylor April 17 LCS, Knapsack,
Intro to NP
Consider the code that we finished with for the Knapsack problem: Knapsack(S[1...n], K)
Initialize Table[0..K] = -1 everywhere
Table[0] = 0
for(i = 1 to n)
    for(j = K downto 1)
        if(Table[j] < 0 and j >= S[i] and Table[j-S[i]] >= 0)
            Table[j] = i 

It produces a Table (indices 0 to n) such that, if Table[j] < 0, then a Knapsack of size j cannot be filled with the given items. On the other hand, if the value is non-negative, it will be the smallest possible maximum index used to fill a knapsack of the given size.

Given S[1,2,3,4] = 2, 6, 3, 8 and K=14, show the table after the code above runs. Also, give code so that, given the table and S[], you can reconstruct the knapsack of the given size in time proportional to the number of items that fill it.

Apr 25 Taylor April 22 Definition of "efficiently solvable",
P, NP, and the Vertex Cover, Independent Set, and Clique problems.
  1. Read 34 intro, 34.2, the first 3 pages of 34.3, the definition of 3-CNF-SAT on p. 1082, 34.5.1, and 34.5.2. (34.1, which you are skipping, introduces the notation <G> denoting a binary encoding of G, and the concept of a “formal language”, which is simply a set of binary strings—such as all encodings of a problem that fulfill a particular property. To “decide a language” means to have an algorithm that tells whether or not an encoded problem fulfills the property.)
  2. Written homework 20: Do 34.2-1, 34.2-10
  3. The final programming assignment is here.
  4. This is the last of your homework for the class.
Apr 30 Taylor April 24 NP, co-NP, P relations
PRIME vs COMPOSITE (intro)
Graph Isomorphism,
Vertex Cover to Dominating Set

Bring questions for next week, your ``review'' is just me answering questions you pose.

May 2 Taylor April 29 Review and practice In case you want extra practice questions, I have added them here.
May 7 Taylor May 1 Review and practice
May 9 Review and practice
May 16 09:45-12:00 Final exam