456-0521/01 – Introduction to Algorithms (ZAL)

Gurantor departmentDepartment of Computer ScienceCredits6
Subject guarantordoc. Mgr. Jiří Dvorský, Ph.D.Subject version guarantordoc. Mgr. Jiří Dvorský, Ph.D.
Study levelundergraduate or graduateRequirementCompulsory
Year1Semesterwinter
Study languageCzech
Year of introduction1999/2000Year of cancellation2008/2009
Intended for the facultiesFEIIntended for study typesBachelor
Instruction secured by
LoginNameTuitorTeacher giving lectures
ABD006 Ing. Hussam Abdulla, Ph.D.
CHO247 Ing. Peter Chovanec, Ph.D.
DVO26 doc. Mgr. Jiří Dvorský, Ph.D.
GAJ03 doc. Ing. Petr Gajdoš, Ph.D.
HLA168 Ing. Lukáš Hlaváček
KRO183 Ing. Martin Krolikowski
MIN01 Ing. Marian Mindek, Ph.D.
OH140 RNDr. Eliška Ochodková, Ph.D.
PLA06 doc. Ing. Jan Platoš, Ph.D.
SIK107 Ing. Rostislav Sikora
VYM036 Ing. Michal Výmola
Extent of instruction for forms of study
Form of studyWay of compl.Extent
Full-time Credit and Examination 2+2
Combined Credit and Examination 2+2

Subject aims expressed by acquired skills and competences

The goal of course is introduction to sorting, and searching algorithms, and data structures. Another goal of this course is student's ability to write simple program, using these algorithms and data structures. Student will be able to write simple object oriented applications using abstract data structures.

Teaching methods

Summary

This course can be understood as introduction to algorithms or introduction to programming itself. Basic algorithms of sorting, searching, and elementary data structures will be presented. Students in computer laboratory work on their project with supplement of assistant.

Compulsory literature:

Studijní opora (skripta) pro ZAL Wirth, N.: Algoritmy a štruktúry údajov, Alfa, Bratislava 1989. Sedgewick R.: Algoritmy v C, části 1-4, SoftPress, Praha, 2003 Existuje i v anglické verzi, náročná, ale vynikající kniha. Wróblewski P.: Algoritmy. Datové struktury a programovací techniky, Computer Press, Praha 2003

Recommended literature:

Topfer, P.: Algoritmy a programovací techniky, Prometheus, Praha 1995. Virius, M.: Základy algoritmizace, ČVUT Praha, 1997, skripta. Honzík, J. a kolektiv: Programovací techniky, VUT Brno, 1987, skripta. Harel, D.: Algorithmics, The Spirits of Computing, Addison-Wesley Publishing Company, 1993. Sedgewick, R.: Algorithms in C++, Addison-Wesley Publishing Company, 1992. Wood, D.: Data Structures, Algorithms and Performance, Addison-Wesley Publishing Company, 1993. Cormen, Leiserson, Rievest: Introduction to Algorithms, MIT Press, 2001. Obecně jakákoliv učebnice jazyka Java.

Way of continuous check of knowledge in the course of semester

Conditions for credit: Student must reach at least 21 points from 40 point to get credit (zapocet). Student must obtain at least 5 point of 10 from programming test and at least 16 points out of 30 from project. Exam is written and student can achieve 60 points, at least 30 points.

E-learning

Další požadavky na studenta

Prerequisities

Subject has no prerequisities.

Co-requisities

Subject has no co-requisities.

Subject syllabus:

Lectures: Introductory lesson Concept of algorithm, complexity of algorithm Linear data structures - stack, queue, list Sorting I. Sorting II. Binary search trees I. Binary search trees II. Balanced binary search trees - Red-black trees, B-trees. Hashing Pattern matching I. Pattern matching II. Advanced data structures - skip-list, splay trees (optionally) Exercises: Implementation of examples corresponding to lessons. Projects: Each student will implement one project during the term. Computer labs: Students work on thier project and on examples corresponding to current lesson. Java programming revision Searching in array - linear search, binary search Implementation of stack (queue, list), Bracket parity checking Implementation of O(n2) sorting algorithm Implementation of O(nlogn) sorting algorithm, implementation using Comparable interface Binary search trees - implementation of operations Insert and Search Binary search trees - tree traversal algorithms, counting of nodes etc. Complex example of usage of binary search trees Implementation of hash table, hash function design and tests Pattern matching algorithms Work on term project

Conditions for subject completion

Combined form (validity from: 1960/1961 Summer semester, validity until: 2008/2009 Summer semester)
Task nameType of taskMax. number of points
(act. for subtasks)
Min. number of points
Exercises evaluation and Examination Credit and Examination 100 (100) 51
        Exercises evaluation Credit 20 (20) 0
                Written exam Written test 20  0
        Examination Examination 80 (80) 0
                Written examination Written examination 80  0
Mandatory attendence parzicipation:

Show history

Occurrence in study plans

Academic yearProgrammeField of studySpec.FormStudy language Tut. centreYearWSType of duty
2008/2009 (B2646) Information Technology (1103R021) Computation Mathematics P Czech Ostrava 1 Compulsory study plan
2008/2009 (B2646) Information Technology (1103R021) Computation Mathematics K Czech Ostrava 1 Compulsory study plan
2008/2009 (B2647) Information and Communication Technology (1103R031) Computational Mathematics P Czech Ostrava 1 Compulsory study plan
2008/2009 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology P Czech Ostrava 1 Compulsory study plan
2008/2009 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology P Czech Ostrava 1 Compulsory study plan
2008/2009 (B2647) Information and Communication Technology (2612R059) Mobile Technology P Czech Ostrava 1 Compulsory study plan
2008/2009 (B2647) Information and Communication Technology P Czech Ostrava 1 Compulsory study plan
2008/2009 (B2647) Information and Communication Technology (1103R031) Computational Mathematics K Czech Ostrava 1 Compulsory study plan
2008/2009 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology K Czech Ostrava 1 Compulsory study plan
2008/2009 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology K Czech Ostrava 1 Compulsory study plan
2008/2009 (B2647) Information and Communication Technology (2612R059) Mobile Technology K Czech Ostrava 1 Compulsory study plan
2008/2009 (B2647) Information and Communication Technology K Czech Ostrava 1 Compulsory study plan
2007/2008 (B2646) Information Technology (1103R021) Computation Mathematics P Czech Ostrava 1 Compulsory study plan
2007/2008 (B2646) Information Technology (1103R021) Computation Mathematics K Czech Ostrava 1 Compulsory study plan
2007/2008 (B2646) Information Technology (2612R025) Computer Science and Technology P Czech Ostrava 1 Compulsory study plan
2007/2008 (B2646) Information Technology (2612R025) Computer Science and Technology K Czech Ostrava 1 Compulsory study plan
2007/2008 (B2646) Information Technology (2612R059) Mobile Technology P Czech Ostrava 1 Compulsory study plan
2007/2008 (B2646) Information Technology (2612R059) Mobile Technology K Czech Ostrava 1 Compulsory study plan
2007/2008 (B2647) Information and Communication Technology (1103R031) Computational Mathematics P Czech Ostrava 1 Compulsory study plan
2007/2008 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology P Czech Ostrava 1 Compulsory study plan
2007/2008 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology P Czech Ostrava 1 Compulsory study plan
2007/2008 (B2647) Information and Communication Technology (2612R059) Mobile Technology P Czech Ostrava 1 Compulsory study plan
2007/2008 (B2647) Information and Communication Technology (1103R031) Computational Mathematics K Czech Ostrava 1 Compulsory study plan
2007/2008 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology K Czech Ostrava 1 Compulsory study plan
2007/2008 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology K Czech Ostrava 1 Compulsory study plan
2007/2008 (B2647) Information and Communication Technology (2612R059) Mobile Technology K Czech Ostrava 1 Compulsory study plan
2006/2007 (B2646) Information Technology (1103R021) Computation Mathematics P Czech Ostrava 1 Compulsory study plan
2006/2007 (B2646) Information Technology (1103R021) Computation Mathematics K Czech Ostrava 1 Compulsory study plan
2006/2007 (B2646) Information Technology (2612R025) Computer Science and Technology P Czech Ostrava 1 Compulsory study plan
2006/2007 (B2646) Information Technology (2612R025) Computer Science and Technology K Czech Ostrava 1 Compulsory study plan
2006/2007 (B2646) Information Technology (2612R059) Mobile Technology P Czech Ostrava 1 Compulsory study plan
2006/2007 (B2646) Information Technology (2612R059) Mobile Technology K Czech Ostrava 1 Compulsory study plan
2006/2007 (B2647) Information and Communication Technology (1103R031) Computational Mathematics P Czech Ostrava 1 Compulsory study plan
2006/2007 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology P Czech Ostrava 1 Compulsory study plan
2006/2007 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology P Czech Ostrava 1 Compulsory study plan
2006/2007 (B2647) Information and Communication Technology (2612R059) Mobile Technology P Czech Ostrava 1 Compulsory study plan
2006/2007 (B2647) Information and Communication Technology (1103R031) Computational Mathematics K Czech Ostrava 1 Compulsory study plan
2006/2007 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology K Czech Ostrava 1 Compulsory study plan
2006/2007 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology K Czech Ostrava 1 Compulsory study plan
2006/2007 (B2647) Information and Communication Technology (2612R059) Mobile Technology K Czech Ostrava 1 Compulsory study plan
2005/2006 (B2646) Information Technology (1103R021) Computation Mathematics P Czech Ostrava 1 Compulsory study plan
2005/2006 (B2646) Information Technology (2612R025) Computer Science and Technology P Czech Ostrava 1 Compulsory study plan
2005/2006 (B2646) Information Technology (2612R025) Computer Science and Technology K Czech Ostrava 1 Compulsory study plan
2005/2006 (B2646) Information Technology (1103R021) Computation Mathematics K Czech Ostrava 1 Compulsory study plan
2005/2006 (B2646) Information Technology (2612R059) Mobile Technology P Czech Ostrava 1 Compulsory study plan
2005/2006 (B2646) Information Technology (2612R059) Mobile Technology K Czech Ostrava 1 Compulsory study plan
2004/2005 (B2646) Information Technology (1103R021) Computation Mathematics P Czech Ostrava 1 Compulsory study plan
2004/2005 (B2646) Information Technology (2612R025) Computer Science and Technology P Czech Ostrava 1 Compulsory study plan
2004/2005 (B2646) Information Technology (2612R025) Computer Science and Technology K Czech Ostrava 1 Compulsory study plan
2004/2005 (B2646) Information Technology (1103R021) Computation Mathematics K Czech Ostrava 1 Compulsory study plan
2004/2005 (B2646) Information Technology (2612R059) Mobile Technology P Czech Ostrava 1 Compulsory study plan
2004/2005 (B2646) Information Technology (2612R059) Mobile Technology K Czech Ostrava 1 Compulsory study plan
2003/2004 (B2646) Information Technology (1103R021) Computation Mathematics P Czech Ostrava 1 Compulsory study plan
2003/2004 (B2646) Information Technology (2612R025) Computer Science and Technology P Czech Ostrava 1 Compulsory study plan
2003/2004 (B2646) Information Technology (2612R025) Computer Science and Technology K Czech Ostrava 1 Compulsory study plan
2003/2004 (B2646) Information Technology (1103R021) Computation Mathematics K Czech Ostrava 1 Compulsory study plan

Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner