I500/B609:
Fundamental Computer Concepts of Informatics
Fall Semester 2016
Lecture : MW 8:00a-9:15a, Rm: BH 005
Office Hour: T 2-3:30p or by appointment (Tang, LH 301D).
Th 5-6p Informatics connecting building (Abhishek Kumar)
Lab: Thursdays, 3:35-4:25p, Rm G Y226 25 seats
and Fridays, 2:30-3:20p, Rm WY 125 20 seats
Final Exam: 8:30-10:00am Wed., December 14, Rm: BH 005
Instructor: Haixu Tang.
AI: Chao Tao (taochao@iu.edu) and Abhishek Kumar (ak8@umail.iu.edu)
Description: The objective of the course is to
study the principles for the design and analysis of efficient algorithms.
A significant portion of the course will be devoted to the introduction of programming in C/C++. No prior programming experience is expected.
The important themes that will be covered by this course include
- Basic principles for algorithm design
- Analysis of algorithms and asymptotic notations
- Recurrences
- Sorting and order statistics
- Elementary data structures
- Hash tables and binary search trees
- Greedy algorithms
- Dynamic programming
- Amortized analysis
- Matroids
- Advance data structures: B-trees, Binomial heaps and Fibonacci heaps
- Randomized algorithms
- String matching algorithms
- Graph algorithms
- Maximum flow
- Linear programmging
This class will have a separate lab section, in which the students will be guided
to implement the algorithms that are covered in the class.
This course is designed for graduate students in bioinformatics (or in other computational science research areas) without computer science background. Graduate students with biology major who is interested in bioinformatics applications are also welcome to take this course. In this year, I will adopt a problem-based learning approach. The students will be required to watch education videos on basic topics before each week's lecture, while the I will focus on the discussion on more advanced topics and their applications. I will also spend time on problem-solving skills, in particular how to formulate computiational problems and develop efficient algorithms from practical applications.
Textbook: :
T. H. Corman, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to algorithms.
, 3rd edn, The MIT Press, 2009 1-2, 4, 9 3.1-3.2,4.1-4.3 6-8 16 12-14 18 19-20 22, 17 21, 22-25 26 5 29 32 Last updated : 6/30/2016
Assignments: We will have 5 take-home
assignments.
Grading: Combined
assignments (25%), Lab/programming exercise (10%), One mid-term exam (30%), Final exam (30%), Attendence (5%).
Office hour: Haixu Tang: T 2-3:30pm, or upon appointment
Prerequisites: College calculus or to talk to the instructors.
Important As your instructor, one of my responsibilities is
to help create a safe learning environment on our campus.
Title IX and our own Sexual Misconduct policy prohibit sexual misconduct.
If you have experienced sexual misconduct, or know someone who has, the University can help.
I encourage you to visit http://stopsexualviolence.iu.edu/ to learn more.
If you are seeking help and would like to speak to someone confidentially,
you can make an appointment with a Mental Health Counselor on campus
(contact information available at http://stopsexualviolence.iu.edu/employee/confidential.html).
It is also important that you know that federal regulations and University policy require me to promptly
convey any information about potential sexual misconduct known to me to our Deputy
Title IX Coordinator or IU’s Title IX Coordinator. In that event, they will
work with a small number of others on campus to ensure that appropriate measures are
taken and resources are made available to the student who may have been harmed.
Protecting a student’s privacy is of utmost concern, and all involved will only share information
with those that need to know to ensure the University can respond and assist.
Preliminary syllabus [This may change!]:
Week
Contents
Lecture
notes
1
Introduction to the class;
introduction to C programming;
Divide and Conquer algorithms (multiplication of n-bit numbers, Strassen's algorithm, selection problem)
Lab 1
2
Self-learning topics: Insertion sort; Merge sort
Lecture topics: Asymptotic notations; Recurrences; Master theorem
Lab 2
3
Self-learning topics: Heaps and heap sorting; Quicksort; Sorting in linear time
Leture topics: review of sorting algorithms
Lab 3
4
Self-learning topics: Elementary data structures; Hash table
Leture topics: Amortized analysis
Lab 4
5
Self-learning topics: Binary search trees;
Leture topics: Red-black tree
Lab 5
6
Self-learning topics: Dynamic programming
Leture topics: B-trees;
Lab 6
7
Self-learning topics: Greedy algorithm
Leture topics: Binomial heap and Fibonacci heap
8
Mid-term exam
9
Self-learning topics: Elementary graph algorithms
Lecture topics: Matroid theory
Lab 7
10
Self-learning topics: Minimum spanning trees; Shortest paths (Dijkstra's algorithm); All-pairs shortest paths (Floyd algorithm)
Lecture topics: Review of graph algorithms; Data structures for disjoint sets
Lab 8
11
Self-learning topics: Maximum flow
Lecture topics: Push-relabel algorithms
Lab 9
12
Lecture topics: randomized algorithms
Lab 10
13
Lecture topics: Linear programming
Lab 11
14
Lecture topics: String matching algorithms
Lab 12
15
review
16
Final exam