The form the schedule of performance and delivery of works

SYLLABUS

Discipline: CS106 Introduction to Elementary Algorithms

Number of credits: 2 credits

Term: Spring 2011

Instructor’s full name: MSc Satabaldiyev A.B.

Information on the instructor	Time and place	Contact information
Room	Office hours (TSIS)	Tel.:
Satabaldiyev A.B.		By appointment	2297774 (ext.114)

Pre-requisites

Math153 Introduction to Mathematical Logic, CS101 Algorithms and programming languages

Course goals and objectives

¢This course introduces students to the analysis and design of computer algorithms.

¢After year of studying students will improve their programming language skills.

Literature

Introduction to Algorithms, Second Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein

2. Data Structures and Algorithms. Reading, MA: Addison-Wesley, 1983.
Revised and more elementary version of the first six chapters of The Design and Analysis of Computer Algorithms.

3.Knuth, Donald E. The Art of Computer Programming. 3rd ed.
Encyclopedic work in three volumes: (1) Fundamental Algorithms, (2) Seminumerical Algorithms, and (3) Sorting and Searching.

4.Internet resources:

http://www.algoprog.kz http://www.acmp.ru http://www.acm.uva.es

Course Structure:

Total: 14 weeks - Jan 17, 2011 – May 21, 2011

Lectures – 2 h/wk

Lab session – 1 h/wk

Grading criteria

Types of tasks	Grading percentage
Attendance and participation	10%
Laboratory works	12%
Quizzes	10%
SSS	15%
SSSI	12%
Mid-term exam	16%
Final exam	25%
Total	100%

The form the schedule of performance and delivery of works

№

Type of evaluation

Week

Attendance and participation

*

*

*

*

*

*

*

*

*

*

*

*

*

*

Laboratory works

*

*

*

*

*

*

*

*

*

*

*

*

*

Quizzes

*

*

SSS

*

*

*

*

*

*

*

*

*

*

*

*

*

SSSI

*

*

*

*

*

*

*

*

*

*

*

*

*

Mid-term exam

*

Final exam

*

Total

LECTURE PLANS

Week	Name of topic	SSS	SSSI
	Introduction ·Course Objectives ·Grading Policy ·Collaboration Policy ·Loops	Assignment #1	- “perfect” numbers - palindrome - longest “zero” sequence - sum of digits
	Arrays and basic sorting algorithms ·Revision of a first contest ·Arrays ·Sorting(Bubble, Selection, Insertion) ·Two-dimentional arrays	Assignment #2	- set intersection - time sorting - a year balance problem - painter problem
	Recursion I ·Contest's tiny points ·Recursion ·The Fibonnaci sequence ·The Towers of Hanoi ·The Labyrinth problem	Assignment #3	- sum of two numbers - box problem - finding the shortest path from labyrinth
	Recursion II ·Euclidian algorithm ·QuickSort ·MergeSort ·Basic Combinatorics	Assignment #4	- half sorting problem - bus ticket operation - huge gcd
	Data structures ·Stack ·Examples on Stack ·Queue ·Examples on Queue	Assignment #5	- polish notation - correct bracket sequence - next greater number - two knights
	Basic geometry ·Coordinate plane ·Area of a triangle and polygon ·Point in a triangle ·Lines intersection ·Comparing double values	Assignment #6	- Finding intersection of two lines - Shooter problem - Area of a polygon
	Heaps and Heap Sort ·Binary trees ·Heap properties ·Insertion and deleteing minimum number ·Heapsort	Assignment #7	- building min and max heap from an array - implementation of min_heapify method.
	Midterm Examination
	Dynamic Programming I ·General overview ·Top-down approach ·Bottom-up approach ·Common characteristics	Assignment #8	- knapsack problem - monkey and bananas problem - investment possibilities
	Dynamic Programming II ·Equipment replacement ·Nonadditive recursions ·“Linear” decision-making	Assignment #9	- longest increasing subsequence - optimal strategy for a game - box stacking
	Asymptotic analysis Introduction “Big Oh” notation “Omega” notation “Theta” notation	Assignment #10	- solve problems from 192.168.0.8/~askar/introduction-to-algorithms/week11/
	Introduction to Graph Theory ·Definitions and notations ·Depth-first search ·Breadth-first search	Assignment #11	- Krypton factor - Trip routing - Theseus and the Minotaur
	Graph Theory II ·Prim's algorithm ·Kruskal's algorithm ·Nearest neighbour algorithm	Assignment #12	- Getting in Line - Edge Coloring - Border
	Graph Theory III ·Bellman-Ford algorithm ·Dijkstra's algorithm ·Ford-Fulkerson algorithm	Assignment #13	- Shipping Routes - Oil Deposits - Street Directions
	Final Examination

List of labs

N week	Name of the topic	Name of Labs
	Loops	http://www.algoprog.kz ACC #1
	Arrays	http://www.algoprog.kz ACC #2
	Recursion I	http://www.algoprog.kz ACC #3
	Recursion II	http://www.algoprog.kz ACC #4
	Data Structures	http://www.algoprog.kz ACC #5
	Basic Geometry	http://www.algoprog.kz ACC #6
	Heap, HeapSort	http://www.algoprog.kz ACC #7
8 9	Dynamic Programming I	http://www.algoprog.kz ACC #8
	Dynamic Programming II	http://www.algoprog.kz ACC #9
	Asymptotic Analysis	http://www.algoprog.kz ACC #10
	Introduction to Graph Theory	http://www.algoprog.kz ACC #11
	Graph Theory I	http://www.algoprog.kz ACC #12
	Graph Theory II	http://www.algoprog.kz ACC #13

Knowledge control forms:

Quizes: 2 times in a semester

Midterm Examination: 1 time in a semester

Final Examination: 1 time in a semester, within period of examination session

Дата добавления: 2015-10-30