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

Gurantor department	Department of Computer Science	Credits	5
Subject guarantor	doc. Mgr. Jiří Dvorský, Ph.D.	Subject version guarantor	doc. Mgr. Jiří Dvorský, Ph.D.
Study level	undergraduate or graduate
		Study language	English
Year of introduction	2023/2024	Year of cancellation
Intended for the faculties	FEI	Intended for study types	Bachelor

Instruction secured by
Login	Name	Tuitor	Teacher giving lectures
DVO26	doc. Mgr. Jiří Dvorský, Ph.D.
SEN0042	prof. Ing. Roman Šenkeřík, Ph.D., DBA

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

To introduce students to problem solving techniques using algorithms. Upon completion of the course, the student will be able to: define and describe selected problem solving algortihmic techniques using, demonstrate these techniques on sample problems use these techniques to solve other problems, work with combinations of several techniques together.

Teaching methods

Lectures
Tutorials

Summary

This course is one of the introductory programming courses. The course aims to introduce students to problem solving techniques, strategies, using algorithms. The algorithms and data structures discussed will be demonstrated in C++. Students are encouraged to analyze algorithmic problems and to synthesize solutions from 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. Completion of several homework assignments.

E-learning

Other requirements

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

Prerequisities

Subject code	Abbreviation	Title	Requirement
460-2052	UPR	Introduction to Programming	Recommended
460-2054	FPR	Functional Programming	Recommended

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: 2023/2024 Winter semester)

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

Mandatory attendence participation: Attendance at exercises is compulsory and is monitored. The scope of the compulsory attendance will be communicated to the students by the course supervisor at the beginning of the semester.

Show history

Conditions for subject completion and attendance at the exercises within ISP: Course completion requirements - Completion of all mandatory tasks within individually agreed deadlines. Attendance at exercises - The level of attendance at exercises is agreed by the student with the course supervisor at the beginning of the semester.

Show history

Occurrence in study plans

Academic year	Programme	Branch/spec.	Spec.	Zaměření	Form	Study language	Tut. centre	Year	W	S	Type of duty
2024/2025	(B0613A140010) Computer Science			TZI	P	English	Ostrava	1			Compulsory	study plan
2023/2024	(B0613A140010) Computer Science			TZI	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

Assessment of instruction

Předmět neobsahuje žádné hodnocení.