Data Structures and Algorithms

San José State University — Computer Science Department — CS 146 sections 5 and 6 — Spring 2017



Schedule

This schedule is tentative and subject to change during the semester. Changes will be reflected on this page as well as announced during lecture. Students should consult this schedule regularly for the most up-to-date information.

Date Topic Reading Homework
Th 1/26 Introduction [slides] 1.1, 1.2 (skim)  
T 1/31 Recursion: simplify-and-delegate [slides] [code]    
Th 2/2 Analysis: O-notation [slides] O and Θ - 3.1  
T 2/7 Last day to drop
Recursion: Towers of Hanoi, binary tree [slides] [code]
Binary trees - 10.4  
Th 2/9 Analysis: time and space complexity [slides] Space complexity  
S 2/12     Hw 1 due
Hw 1 solutions
T 2/14 Data structures: abstract data types [slides]
Data structures: sorted set ADT
Problem solving techniques
Java interfaces and implementations
Java SortedSet interface
Problem solving techniques
 
Th 2/16 Last day to add
Data structures: sorted set implementations [slides]
skiplist, binary search tree
Skiplists - UMD slides
Binary search trees - Ch 12
 
S 2/19     Hw 2 due
Hw 2 solutions
T 2/21 Recursion: backtracking [slides] Backtracking - 3.1, 3.3, 3.6 - Erickson  
Th 2/23 Data structures: dictionary ADT [slides]
Graph representation, caching and memoization
Representation of graphs - 22.1 and/or
Adjacency list - Wikipedia
Memoization - Wikipedia
 
S 2/26     Hw 3 due
Hw 3 solutions
T 2/28 Data structures: priority queue ADT (part 1) [slides]
breadth-first search, Dijkstra’s algorithm
Priority queues - 6.5 (p 162 only)
Breadth-first search - 22.2
Dijkstra’s algorithm - 24.3
 
Th 3/2 Data structures: priority queue ADT (part 2) [slides]
MST algorithms
Minimum spanning trees - Ch 23  
S 3/5     Hw 4 due
Hw 4 solutions
T 3/7 Recursion: divide-and-conquer algorithms [slides] 2.3 - mergesort
Ch 4 intro and 4.1 - max subarray sum
Karatsuba’s algorithm - Wikipedia
 
Th 3/9 Analysis: recurrence equations [slides] Recursion tree method - 4.4  
S 3/12     Hw 5 due
Hw 5 solutions
T 3/14 Exam 1: covers hw 1-4    
Th 3/16 Data structures: red-black trees [slides] Ch 13  
S 3/19     Hw 6 due
Hw 6 solutions
T 3/21 Exam 1 solutions, red-black trees wrap-up    
Th 3/23 Data structures: stacks ADT (part 1) [slides]
Depth-first search, Graham scan
Stacks - 10.1
Depth-first search - 22.3
Finding the convex hull - 33.3
 
S 3/26     Hw 7 not due
T 3/28 Spring recess    
Th 3/30 Spring recess    
S 4/2     Hw 7 due
Hw 7 solutions
T 4/4 Data structures: stacks ADT (part 2) [slides]
Strongly connected components
Strongly connected components - 22.5  
Th 4/6 Data structures: hashing [slides] 11.1-11.4  
S 4/9     Hw 8 due
Hw 8 solutions
T 4/11 Graphs: single-source shortest paths [slides] 24.1-24.2  
Th 4/13 Recursion: dynamic programming (part 1) [slides] 15.1, 15.3
Automatic memoization in Java
Memoization with decorators in Python
 
S 4/16     Hw 9 due
Hw 9 solutions
T 4/18 Recursion: dynamic programming (part 2) [slides] 15.4, 25.2  
Th 4/20 Recursion: quicksort [slides] [code] Ch 7  
S 4/ 23     Hw 10 due
Hw 10 solutions
T 4/25 Exam 2: covers hw 5-9    
Th 4/27 Data structures: priority queue implementation
heap, selection sort and heapsort [slides] [code]
Ch 6  
S 4/30     Hw 11 due
Hw 11 solutions
T 5/2 Hardness: sorting lower bounds [slides] 8.1  
Th 5/4 Hardness: radix sort [slides] [code] 8.3  
S 5/7     Hw 12 due
Hw 12 solutions
T 5/9 Hardness: Computational complexity [slides] Ch 34 (skim)  
Th 5/11 Hardness: approximation algorithms [slides] Ch 35 (skim)  
S 5/14     Hw 13 due
Hw 13 solutions
T 5/16 Review    
T 5/23 Section 5 final exam T 5/23 7:15AM–9:30AM, MH 222
   
W 5/24 Section 6 final exam W 5/24 9:45AM–12:00PM, MH 225    

Exams from Fall 2016

Download here: [zip]

Note: these will give you an idea of the format of the exams, but these may not necessarily be suitable practice questions as the topics may be different and covered in a different order.

Exam 2 topics

For a complete list of what you will be expected to know for the exam, please refer to the descriptions at the beginning of homework 5 through 9. This is what the exam questions will be based on.

For your convenience, here is a succinct list of the topics covered on the exam. Please keep in mind that the authorative study guide are the homework descriptions, not the list below.

What won’t be on the exam