address.jpg

ICE 245: Algorithms



sep.png

Announcements:


Date
Description
Comments
02.05.2016
Introduction of the course
First Meeting on 10.05.2016

sep.png

Course objective:



sep.png

Stuffs:


Dr. Abu Sayed Md. Mostafizur Rahaman
Associate Professor
Lecture: 11:15~13:00 and Wednesday 10:20 ~12:04, CSE-room : 01
Office hours: Saturday ~ Thursday 10:00-16:30
Office: Computer Science and Engineering Building, Ground Floor. Cell: +880 (0)1927 129 603,
Email: asmmr@juniv.edu
Homepage: [[|http://chyon.wikispaces.com]]

sep.png

Syllabus and lecture overview



Syllabus:
The course material includes all the lecture and class drill material, as well as related discussion in the textbook. (This textbook reference means that, whenever a student did not understand something in class but that thing is covered in the textbook in more detail, an understanding is expected. It does not mean that topics that were not discussed in class altogether but are in the book are included.)

Details:
  • Complexity of Algorithms: worst case, average case, and amortized complexity. Algorithm analysis.
  • Lists: stacks, queues, implementation, garbage collection.
  • Dictionaries: Hash tables, binary search trees, AVL trees, red-black trees, splay trees, skip-lists, B-trees. Priority queues.
  • Graphs: Shortest path algorithms, minimal spanning tree algorithms, depth-first and breadth-first search.
  • Sorting: Advanced sorting methods and their analysis, lower bound on complexity, order statistics.
  • Algorithm design paradigms.
sep.png

Reference books:


  • Weiss, Data Structures and Algorithm Analysis in C++, 4th Ed., Addison Wesley.
  • Cormen, Leiserson, and Rivest, Introduction to Algorithms, McGraw Hill, 1990.

sep.png

Grading Policy:



  • TBA

sep.png

Lecture schedule and materials:


1. Introduction and review
S/N
Topics
Date
Download
Remarks
1.1
Introduction



1.2
C++


LAB
1.3
Mathematical induction



2. Algorithm analysis
S/N
Topics
Date
Download
Remarks
2.1
Containers, relations, and abstract data types (ADTs)


LAB
2.2
Data structures and algorithms



2.3
Asymptotic analysis



2.4
Algorithm analysis



3. Lists, stacks, and queues
S/N
Topics
Date
Download
Remarks
3.1
Lists



3.2
Stacks



3.3
Queues



3.4
Deques



3.5
Linked lists



3.6
Node-based storage with arrays



4. Search trees
This topic looks at storing linearly ordered data in search trees. The focus is to ensure that operations on individual elements stored in the tree run in Θ(ln(-)) time.
S/N
Topics
Date
Download
Remarks
4.1
Binary search trees



4.2
AVL trees



4.3
In-order traversals



4.4
Multiway search trees (was M-way trees)



4.5
B+ trees



4.6
Red-Black trees



4.7
k-d trees



4.8
BB[α] trees



4.9
Splay trees



4.10
Average depth of random binary trees



5. Priority queues
A priority queue stores linearly ordered data based on the priority; however, by restricting the operations, those operations can be optimized.
S/N
Topics
Date
Download
Remarks
5.1
Priority queues



5.2
Binary heaps



5.3
d-ary heaps



5.4
Leftist heaps



5.5
Skew heaps



5.6
Binomial heaps



6. Sorting algorithms
S/N
Topics
Date
Download
Remarks
6.1
Introduction to sorting



6.2
Insertion sort



6.3
Bubble sort



6.4
Heap sort



6.5
Merge sort



6.6
Quicksort



6.7
Bucket sort



6.8
Radix sort



6.9
Inversions



6.10
External sorting



7. Hash functions and hash tables

S/N
Topics
Date
Download
Remarks
7.1
Introduction to hash tables



7.2
Hash functions



7.3
Mapping down to 0, ..., M − 1



7.4
Chained hash tables



7.5
Scatter tables



7.6
Open addressing



7.7
Linear probing



7.8
Quadratic probing



7.9
Double hashing



7.10
Poisson distribution



8. Graph algorithms
S/N
Topics
Date
Download
Remarks
8.1
Introduction to graph theory



8.2
Graph data structures



8.3
Graph traversals



8.3a
Connectedness



8.3b
Single source unweighted path length



8.3c
Identifying bipartite graphs



8.4
Topological sort



8.5
Minimum spanning tree algorithms



8.5a
Prim's algorithm



8.5b
Kruskal's algorithm



8.6
Single-source shortest path algorithms



8.6a
Dijkstra's algorithm



8.6b
A* search algorithm



8.6c
Bellman-Ford algorithm




All-pairs shortest path



8.7a
Floyd-Warshall algorithm



8.7b
Johnson's algorithm




Maximum flow algorithms



8.8a
Ford-Fulkerson algorithms



9. Algorithm design
S/N
Topics
Date
Download
Remarks
9.1
Introduction to algorithm design techniques



9.2
Greedy algorithms



9.3
Divide-and-conquer algorithms



9.4
Dynamic programming



9.5
Backtracking algorithms



9.6
Branch-and-bound algorithms




Brute Force Algorithms



9.7
Stochastic algorithms



9.8
Linear Programming



sep.png

Homework assignments:


  • TBA

sep.png

Date of Class Tests :


Test no
Date
Topics
Problem set
Solution
Remarks






sep.png

1. Introduction and review
S/N
Topics
Date
Download
Remarks
1.1
Introduction



1.2
Mathematical review



1.3
C++



1.4
Mathematical induction






2. Algorithm analysis
S/N
Topics
Date
Download
Remarks
2.1
Containers, relations, and abstract data types (ADTs)


LAB
2.2
Data structures and algorithms



2.3
Asymptotic analysis



2.4
Algorithm analysis






3. Lists, stacks, and queues
S/N
Topics
Date
Download
Remarks
3.1
Lists



3.2
Stacks



3.3
Queues



3.4
Deques



3.5
Linked lists



3.6
Node-based storage with arrays






4. Trees and hierarchical orders
Before we proceed with looking at data structures for storing linearly ordered data, we must take a diversion to look at trees. At first glance, it appears as if trees are most appropriate for storing hierarchically ordered data; however, we will later see how trees can also be used to allow efficient storage of linearly ordered data, as well.
4.1
Introduction to trees
pptx
pdf
V
Q
-

W
D
-
4.2
Abstract trees
pptx
pdf
V
Q
-

W
-
-
4.3
Tree traversals
pptx
pdf
V
Q
-

W
D
-
4.4
Parental trees
pptx
-
-
-
-
Optional
W
-
-
4.5
Forests
pptx
-
-
-
-
Optional
W
-
-
4.6
The mechanism of recursion, part 1
pptx
-
-
-
-
Optional
W
-
-



5. Search trees
This topic looks at storing linearly ordered data in search trees. The focus is to ensure that operations on individual elements stored in the tree run in Θ(ln(-)) time.
S/N
Topics
Date
Download
Remarks
6.1
Binary search trees



6.2
AVL trees



6.3
In-order traversals



6.4
Multiway search trees (was M-way trees)



6.5
B+ trees



6.6
Red-Black trees



6.7
k-d trees



6.8
BB[α] trees



6.9
Splay trees



6.10
Average depth of random binary trees






6. Priority queues
A priority queue stores linearly ordered data based on the priority; however, by restricting the operations, those operations can be optimized.
S/N
Topics
Date
Download
Remarks
7.1
Priority queues
pptx
pdf
-
7.2
Binary heaps
pptx
pdf
-
7.3
d-ary heaps
pptx
-
-
7.4
Leftist heaps
pptx
-
-
7.5
Skew heaps
pptx
-
-
7.6
Binomial heaps
pptx
-
-



7. Sorting algorithms
S/N
Topics
Date
Download
Remarks
8.1
Introduction to sorting



8.2
Insertion sort



8.3
Bubble sort



8.4
Heap sort



8.5
Merge sort



8.6
Quicksort



8.7
Bucket sort



8.8
Radix sort



8.9
Inversions



8.10
External sorting






8. Hash functions and hash tables
Note that previously I used to teach linear probing and double hashing; however, it has been brought to my attention that quadratic hashing is better—especially when we consider the effects of caching and the additional cost of cache misses.
S/N
Topics
Date
Download
Remarks
9.1
Introduction to hash tables



9.2
Hash functions



9.3
Mapping down to 0, ..., M − 1



9.4
Chained hash tables



9.5
Scatter tables



9.6
Open addressing



9.7
Linear probing



9.8
Quadratic probing



9.9
Double hashing



9.10
Poisson distribution






9. Graph algorithms
S/N
Topics
Date
Download
Remarks
11.1
Introduction to graph theory



11.2
Graph data structures



11.3
Graph traversals



11.3a
Connectedness



11.3b
Single source unweighted path length



11.3c
Identifying bipartite graphs



11.4
Topological sort



11.5
Minimum spanning tree algorithms



11.5a
Prim's algorithm



11.5b
Kruskal's algorithm



11.6
Single-source shortest path algorithms



11.6a
Dijkstra's algorithm



11.6b
A* search algorithm



11.6c
Bellman-Ford algorithm



11.7
All-pairs shortest path



11.7a
Floyd-Warshall algorithm



11.7b
Johnson's algorithm



11.8
Maximum flow algorithms



11.8a
Ford-Fulkerson algorithms






10. Algorithm design
S/N
Topics
Date
Download
Remarks
12.1
Introduction to algorithm design techniques



12.2
Greedy algorithms



12.3
Divide-and-conquer algorithms



12.4
Dynamic programming



12.5
Backtracking algorithms



12.6
Branch-and-bound algorithms



12.7
Stochastic algorithms