460-2001/06 – Algorithms I (ALG I)

Gurantor department	Department of Computer Science	Credits	4
Subject guarantor	doc. Mgr. Jiří Dvorský, Ph.D.	Subject version guarantor	doc. Mgr. Jiří Dvorský, Ph.D.
Study level	undergraduate or graduate	Requirement	Compulsory
Year	2	Semester	summer
		Study language	English
Year of introduction	2019/2020	Year of cancellation
Intended for the faculties	FEI	Intended for study types	Bachelor

Instruction secured by
Login	Name	Tuitor	Teacher giving lectures
ABD006	Ing. Hussam Abdulla, Ph.D.
DVO26	doc. Mgr. Jiří Dvorský, Ph.D.

Extent of instruction for forms of study
Form of study	Way of compl.	Extent
Full-time	Graded credit	2+2

Subject aims expressed by acquired skills and competences

Acquaint students with the basics of structured programming, the basics of C + +. After completing the course, students will be able to: Work with integrated development environment for C++. Define a describe basic programming constructions. Develop and debug a simple program C++. Use data structures such as array, list, etc. Write a recursive function. Use sorting and searching algorithms in their programs.

Teaching methods

Lectures
Tutorials

Summary

This subject is the introductory programming course. Students are expected to have the basic C++ knowledge and high school math knowledge. Discussed algorithms and data structures will be demonstrated in C++. A large emphasis is placed on practical implementation discussed algorithms and data structures. Students are encouraged analysis and synthesis solutions to the problems of smaller units.

Compulsory literature:

LEVITIN, Anany. Introduction to the design. 3rd ed. Boston: Pearson, 2012. ISBN 978-0-13-231681-1. CORMEN, Thomas H. Introduction to algorithms. 2nd ed. Cambridge, Mass.: MIT Press, 2001. ISBN 02-620-3293-7. SEDGEWICK, Robert. Algorithms in C. 3rd ed. Reading, Mass: Addison-Wesley, 1998. ISBN 978-020-1350-883.

Recommended literature:

STROUSTRUP, Bjarne. The C programming language. Fourth edition. Upper Saddle River, NJ: Addison-Wesley, 2013. ISBN 978-0321563842. SCHILDT, Herbert. Teach yourself C. 3rd ed. Berkeley: Osborne McGraw-Hill, 1998. ISBN 978-0078823923.

Way of continuous check of knowledge in the course of semester

Conditions for granting credit Implementation and presentation of the project. Programming applications to simple exercises. Attendance on exercises.

E-learning

Other requirements

Students are expected to have the basic C++ knowledge and high school math knowledge.

Prerequisities

Subject has no prerequisities.

Co-requisities

Subject has no co-requisities.

Subject syllabus:

Algorithm. Algorithmic problem solving strategies. Important problem types. Analysis of complexity of algorithms. Brute force strategy. SelectSort. BubbleSort. Sequential search. Convex hull problem. Closest pair problem. Complete search strategy. Traveling salesman problem. Knapsack problem. Graph traversal. Decrease and conquer strategy. InsertSort. Generate permutations and subsets. Binary search algorithm. Finding the median. Interpolation search. Searching and insertion in a binary search tree. Divide and conquer strategy. QuickSort. MergeSort. Convex hull problem. Closest pair problem. Computer seminars Iterative algorithms complexity analysis. Recursive algorithms complexity analysis. Implementation of convex hull problem, closest pair problem. Traveling salesman problem - experiments with complete search solution. Graph traversal algorithms usage. Generate permutations and subsets. Implementation of binary search algorithm, interpolation search algorithm and median finding. Binary search tree implementation. Implementation of divide and conquer strategy solutions.

Conditions for subject completion

Full-time form (validity from: 2019/2020 Winter semester)

Task name	Type of task	Max. number of points (act. for subtasks)	Min. number of points
Graded credit	Graded credit	100 (100)	51
Ongoing Activity	Other task type	30	15
Project defense	Project	30	15
Final written test	Written test	40	21

Mandatory attendence parzicipation: Every student has to obtain at least the minimum number of points for each task.

Show history

Occurrence in study plans

Academic year	Programme	Zaměření	Form	Study language	Tut. centre	Year	Type of duty
2021/2022	(B0613A140010) Computer Science	TZI	P	English	Ostrava	1	Compulsory	study plan
2021/2022	(B0714A060019) Biomedical Assistive Technology	EaI	P	English	Ostrava	1	Compulsory	study plan
2021/2022	(B0714A150004) Computer Systems for the Industry of the 21st. Century	INF	P	English	Ostrava	2	Compulsory	study plan
2021/2022	(B0541A170009) Computational and Applied Mathematics		P	English	Ostrava	1	Compulsory	study plan
2020/2021	(B0714A150004) Computer Systems for the Industry of the 21st. Century	INF	P	English	Ostrava	2	Compulsory	study plan
2020/2021	(B0714A060019) Biomedical Assistive Technology	EaI	P	English	Ostrava	1	Compulsory	study plan
2020/2021	(B0613A140010) Computer Science	TZI	P	English	Ostrava	1	Compulsory	study plan
2020/2021	(B0541A170009) Computational and Applied Mathematics		P	English	Ostrava	1	Compulsory	study plan
2020/2021	(B0713A060008) Automotive Electronic Systems	SPA	P	English	Ostrava	1	Compulsory	study plan
2019/2020	(B0714A150004) Computer Systems for the Industry of the 21st. Century	INF	P	English	Ostrava	2	Compulsory	study plan
2019/2020	(B3973) Automotive Electronic Systems		P	English	Ostrava	1	Compulsory	study plan
2019/2020	(B0613A140010) Computer Science	TZI	P	English	Ostrava	1	Compulsory	study plan
2019/2020	(B0541A170009) Computational and Applied Mathematics		P	English	Ostrava	1	Compulsory	study plan

Occurrence in special blocks

Block name	Academic year	Form of study	Study language	Year	W	S	Type of block	Block owner
V - ECTS - bc.	2021/2022	Full-time	English				Optional	401 - Study Office	stu. block
V - ECTS - bc.	2020/2021	Full-time	English				Optional	401 - Study Office	stu. block