Data Structures and Algorithms

San José State University — Computer Science Department — CS 146 sections 7 and 8 — Fall 2016



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.

Lecture Date Topic Reading/homework
1 W 8/24 Introduction
Profile and assessment quiz
1.1, 1.2 (skim)
3.1 (O and Θ)
2 M 8/29 Recursion: simplify-and-delegate Ch 2
3 W 8/31 Recursion: Towers of Hanoi, mergesort
Review: summation notation, induction
4.1
  M 9/5 Labor day Homework 1 due Tuesday 9/6
Friday 9/9 at 11:59 pm
4 W 9/7 Recursion: recurrence equations
Review: logarithms, O-notation
4.3
5 M 9/12 Recursion: divide-and-conquer
Review: worse case time complexity
33.4
6 W 9/14 Recursion: backtracking Erickson notes (just 3.1, 3.3, 3.6)
  F 9/16   Homework 2 due Fri 9/16 11:59pm
7 M 9/19 Recursion: dynamic programming 15.1
8 W 9/21 Recursion: dynamic programming  
9 M 9/26 Data structures: roadmap
Data structures: stacks, space complexity of recursive algorithms,
find the convex hull
10.1, 10.2 (skim)
33.3 (Graham scan)
10 W 9/28 Data structures: priority queues, heaps, selection and heapsort
Heapsort code
Ch 6 and/or
Binary heaps (videos 1-4) - Prof Taylor
  F 9/30   Homework 3 due Fri 9/30 11:59pm
Homework 4 due Fri 9/30 11:59pm
11 M 10/3 Exam 1  
12 W 10/5 Data structures: dictionaries, BSTs
BST starter code
12
13 M 10/10 Data structures: red-black trees 13
14 W 10/12 Randomization: hashing 1: hash tables, hash chaining, hash functions 11.1-11.3
  F 10/14   Homework 5
15 M 10/17 Randomization: hashing 2: table resizing (section 8 only), open addressing 11.4
16 W 10/19 Problem solving session  
  F 10/21   Homework 6
17 M 10/24 Randomization: deterministic and randomized quicksort
Review of basic probability, expectation, indicator variables
7.1-7.3
18 W 10/26 Randomization: analysis of randomized quicksort
Proof using indicator variables
7.4
  Su 10/30   Homework 7
19 M 10/31 Graphs: representation, DFS, strongly connected components 22.1, 22.3
20 W 11/2 Exam 2  
21 M 11/7 Graphs: Tarjan’s algorithm for strongly connected components 22.5
22 W 11/9 Graphs: BFS, single-source shortest path problem, Dijkstra 22.2, 24.3
  Su 11/13   Homework 8
23 M 11/14 Graphs: relaxation  
24 W 11/16 Graphs: Bellman-Ford algorithm 24.1-24.2
  Su 11/20   Homework 9
25 M 11/21 Graphs: minimum spanning trees 23.1-23.2
  W 11/23 Non-instructional day  
26 M 11/28 Hardness: sorting and search lower bounds 8.1
27 W 11/30 Exam 3  
  Su 12/4   Homework 10
28 M 12/5 Hardness: radix sort, NP-completeness 8.3, Ch 34 (skim chapter)
29 W 12/7 Hardness: approximation algorithms Ch 35 (skim chapter)
  Su 12/11   Homework 11
Bonus assignment
30 M 12/12 Review  
    Section 7 final exam F 12/16 2:45PM–5:00PM, MH 422
 
    Section 8 final exam W 12/14 9:45AM–12:00PM, MH 422  

Data structures: roadmap

abstract data type (ADT) interface (API) implementations
stack push()
pop()
linked list
contiguous array
dynamic array
queue queue()
dequeue()
linked list
contiguous array
dynamic array
priority queue insert(priority, obj)
get_min()
binary heap
d-ary heap (d=2,4,8,…)
fibonacci heaps
dictionary
aka map
aka associative array
set(key, value)
get(key)=value
is key in dictionary?
hash table
binary search tree
set add(key)
is key in set?
dictionary
bit vector
graph add(node)
add_edge(n1, n2)
neighbors(node)
is n1 a neighbor of n2?
dictionary
adjacency matrix
adjacency list

Various remarks:

  1. dynamic arrays are known as vectors in C++, arraylists in Java and simply arrays in Python.
  2. binary search trees (AVL, red-black, splay trees) allow us to do more than dictionary searches, as the keys are sorted. The API of binary search trees can be extended with: previous() and next(). Binary search trees can also be viewed as a generalization of dynamic arrays in that the data is sorted (by key) but it also strikes a balance between fast insertion and fast lookup.
  3. Our emphasis in this class will be on stacks (today), priority queues (next time), and spend most of our time on dictionaries and graphs, although we will not avoid the other data structures if they come up. Dictionaries are by far the most important data structures. Since hash tables are the most common implementation of dictionaries, the two terms tend to be used interchangeably.