study plan table

Courses

Advanced algorithms

Formal and informal analysis of the memory and time complexity of all data sructures and algorithms taught is an integral part of the course, it is not expicitely listed under particular topics.
1. Asymptotic complexity of algorithms. Graphs, their properties and memory representation.
2. Minimum spanning tree. Union-Find problem.
3. Euler paths. Directed graphs: connectivity, acyclic graphs.
4. Heaps. Fibonacci heap. Heaps performance comparison.
5. Dynamic data structures. Garbage collector.
6. Generating, enumeration aand isomorphism of data structures and combinatorial objects. Permutations, combinations, variations, trees.
7. Generating other combinatorial structures: k-element subsets, Gray code, non-isomorphic graphs.
8. Search in sequences - linear and quadratic interpolation. Median search.
9. Finite automata, implementation, automaton reduction.
10. Regular expressions and text search using regular expressions.
11. Approximate text search using finite automata, dictionary automata.
12. Search in higher dimensions, K-D trees, Quadtree.
13. Search trees: B a B+; 2-3-4 a R-B trees.
14. Search trees: Trie, suffix tree, splay tree.

Exercises and related homeworks are devoted mostly to implementation of lecture topics. Consequently, the themes of each exercise formally correspond to those of respective lecture.

R. Sedgewick: Algoritmy v C, SoftPress 2003,

T. H. Cormen, C. E. Leiserson, R. L. Rievest, C. Stein: Introduction to Algorithms, 2nd ed., MIT Press, 2001

B. Melichar: Jazyky a překlady, Praha , ČVUT 1996

J. E. Hopcroft, R. Motwani, J. D. Ullman: Introduction to Automata Theory, Languages, and Computation, 2nd ed., Addison-Wesley, 2001

Parallel algorithms

1. Introduction to Parallel Computing
2. Principles of Parallel Algorithms Design      
3. Basic Communication Operations      
4. Analytical Modeling of Parallel Algorithms      
5. Sorting      
6. Matrix Algorithms      
7. Algorithms for Linear Algebra, TEST      
8. Parallel Accelerators      
9. Graph Algorithms I.      
10. Graph Algorithms II.      
11. Combinatorial Algorithms      
12. Dynamic Programming      
13. Fast Fourier Transform

1. Introduction to parallel programming, environment setting
2. Introduction to Cpp11 threads      
3. Advanced constructs in Cpp11      
4. Assignment of the semestral work + homework 1      
5. OpenMP - basic constructs      
6. OpenMP - vectorization, parallel sort      
7. Homework 2, deadline for homework 1      
8. Semestral work - consultation      
9. OpenMPI - distributed algorithms      
10. Homework 3, deadline for homework 2      
11. Semestral work - consultation      
12. Presentations of semestral works      
13. deadline for homework 3, student assessment      

1. Ananth Grama, Anshul Gupta, George Karypis, Vipin Kumar: Introduction to Parallel Computing, Second Edition, Addison Wesley, 2003.
2. Kayhan Erciyes: Distributed Graph Algorithms for Computer Networks, Springer, 2013.
3. Georg Hager, Gerhard Wellein: Introduction to High Performance Computing for Scientists and Engineers, CRC Press, 2011.

Theory of Algorithms

1.      Analyzing algorithms and problems, classifying functions by their growth rates, time and space complexity.
2.      Correctness of algorithms, variants and invariants.
3.      Decision problems and optimization problems.
4.      Turing machine and its variants.
5.      Relation between Turing machine and RAM machine.
6.      Classes P and NP.
7.      Reduction and polynomial reduction of problems.
8.      NP-complete problems, Cook's Theorem.
9.      Classes PSPACE and NPSPACE..
10.      Randomized algorithms with polynomial time complexity.
11.      Classes RP and ZZP.
12.      Undecidable problems.
13.     Reserve.

1.      Determining time and space complexity of well known algorithms.
2.      Verifying correctness of algorithms using variants and invariants.
3.      Turing machines.
4.      Polynomial reductions of problems.
5.      Examples of randomized algorithms.
6.      Examples of undecidable problems.

[1]  Kozen, D. C.: The design and Analysis of Algorithms, Springer-Vrelag, 1991
[2]  Harel, D: Algorithmics: The Spirit of Computing, Addison-Wesleyt Inc., Reading MA 2002
[3]  Talbot, J., Welsh, D.: Complexity and Cryptography, Cambridge University Press, 2006

Combinatorial Optimization

1. Introduction to Basic Terms of Combinatorial Optimization, Example Applications and a Test of Preliminary Knowledge
2. Integer Linear Programming - Algorithms
3. Problem Formulation by Integer Linear Programming
4. The Shortest Paths. Problem Formulation by Shortest Paths.
5. Problem Formulation by Shortest Paths.
6. Flows and Cuts - Algorithms and Problem Formulation. Test I.
7. Multicommodity network flows
8. Knapsack Problem and Pseudo-polynomial Algorithms
9. Traveling Salesman Problem and Approximation Algorithms
10. Monoprocessor Scheduling
11. Scheduling on Parallel Processors. Test II.
12. Project Scheduling with Time Windows.
13. Constraint Programming.
14. Reserved

1. Policy and Individual Project Market
2. Introduction to the Experimental Environment and Optimization Library
3. Integer Linear Programming
4.  Individual Project I - Assignment and Problem Classification
5. Modeling Languages for Solving Combinatorial Problems
6. Individual Project II - Related Work and Solution
7. Applications of Network Flows and Cuts
8. Individual Project III - Consultation
9. Test III
10. Scheduling
11. Advanced Methods for Solving Combinatorial Problems
12. Individual Project IV - hand in a code and a written report
13. Ungraded Assessment
14. Reserved

B. H. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms.
Springer, third ed., 2006.

J. Blazevicz, Scheduling Computer and Manufacturing Processes. Springer,
second ed., 2001.

J. Demel, Grafy a jejich aplikace. Academia, second ed., 2002.
TORSCHE http://rtime.felk.cvut.cz/scheduling-toolbox/

Systems on Chip

1.      Main tasks of analogue and digital integrated circuits designer; design methodologies (top down, bottom up), design abstraction levels - Y chart. 
2.      Application specific integrated circuits systems types, full custom design, gate array, standard cells, programmable array logic; main features, economical aspect of the design.
3.      Full customs integrated systems, feasibility study, specification, criteria for technology and design kits selection.
4.      World standards and CAD tools for analog and mix-signal integrated circuits design, design of RF and mobile low power systems.
5.      Design tools for automatic generation of analog behavior models, bottom up design methodology, macro blocks.
6.      Design principles of mix-signal integrated circuits, purpose of hierarchical design, digital and analogue block interface, CAD design tools for automatic circuit generation; functional and static time analysis, formal verification; Verilog-A, Verilog-AMS, VHDL-A. 
7.      Hardware description languages -VHDL, Verilog, Verilog-A, Verilog-AMS.
8.      Design tools and methodologies for digital integrated circuits and systems; language VHDL, Verilog; library cells; parameters extractions for library cells development.
9.      Frond end design - functional specification, RTL, logic synthesis, Gate-level netlist, behavioral stimulus extraction.
10.      Back End design - specification of Design Kit, mapping of the design, Floorplanning, place and route, layout, parasitic extraction, layout versus schema check (LVS).
11.      Methods of physical synthesis, placement of functional blocks, power lines design and distribution, simulation of interconnect continuity, design verification.
12.      Clock signal distribution, delay calculating, static and dynamic timing analysis.
13.      Testing, design of testbenches, design verification methods.
14.      Tape out and fabrication, integrated systems verification, scaling and design mapping to different technologies.

1.      CADENCE design system
2.      CMOS Design kit description, library cells
3.      Demonstration of mix-signal design - hierarchical structuring, design cells abstraction.
4.      Demonstration of mix-signal design - simulations, interface definition, Spectre AMS simulator, corner analysis.
5.      Analogue layout, parasitic extraction, design rule check, postlayout simulation.
6.      Demonstration of mix-signal design - digital flow, back end, frond end.
7.      Digital layout (Back End design), Floorplanning, routing, timing analysis.
8.      Student project - design of mix-signal IC.
9.      Student project - design of mix-signal IC.
10.      Student project - design of mix-signal IC.
11.      Student project - design of mix-signal IC.
12.      Student project - design of mix-signal IC.
13.      Student project - design of mix-signal IC.
14.      Student project presentation, final assessment.

Michael Smith: Application-Specific Integrated Circuits, Addison-Wesley, 1998
P. Gray, P Hurst, s. Lewis, R. Mayer: Analysis and Design of Analog Integrated Circuits, John Wiley and Sons, 2000

Effective Software

NA

NA

NA

Software or Research Project

NA

NA

NA

Advanced Computer Architectures

NA

NA

NA

Computer Communication Interfaces

1.	High-speed parallel and serial interfaces, physical limits
2.	PCI and PCI Express, functional principles, transaction optimization, QoS
3.	Implementation of PCI and PCI Express peripherals
4.	USB ? functional principles
5.	USB ? embedded Master, USB on the go
6.	Technical and economic parameters of implementation of I/O interfaces and peripherals
7.	I/O device drivers for OS Windows and Linux
8.	IEEE802.3, VLAN, auto-negotiation, PoE
9.	Wireless computer networks (WiFi)
10.	TCP/IP stack implementation
11.	Wireless sensor networks, specific MAC and routing algorithms
12.	Energy harvesting in sensor networks
13.	Industrial distributed technologies (EIA-485, EIA-232, CAN, LIN ?)
14.	Reserve

NA

[1] Zurawski, R.: Networked Embedded Systems, CRC Press 2009, ISBN-13: 978-1439807613

Diplomová práce - Diploma Thesis

NA

NA

NA

Application of Embedded Systems

1.  	Architecture of ARM Cortex M processors for embedded systems
2.  	ARM based microcontrollers
3. 	Microcontroller elements and peripherals, electrical parameters of I/O pins
4.  	User interfacing and control
5.  	Actuator interfacing 
6.  	Digital signal processing ? digitalization, sampling, quantization, spectrum, sampling theorem
7.  	Signal generation processing, Direct Digital Synthesis (DDS), signal processors
8.  	Spectrum analysis, FFT ? DFT, correlation function and their use
9.  	Digital filters ? basic types and their use, realization on microcontrollers and DSPs 
10.  	Semiconductor sensors and MEMS, interfacing with embedded systems, information processing
11.  	Image and optoelectronic sensors, image acquisition and its use
12.  	Embedded systems in automotive, wearable, toys etc.
13.  	Embedded systems in smart homes, security, IoT
14.  	Spare

NA

NA