Algorithms 1

Public Resources

 

No login is required.
If provided, read carefully additional texts that can contain some helpful information on the origins of the files, licence agreements, etc.

Internal Resources

 

No login is required. If provided, read carefully additional texts that can contain some helpful information on the origins of the files, licence agreements, etc.

Lesson 1

  • subject conditions
  • recommended IDE (Integrated Development Environment), Microsoft Visual Studio 2015 (VS)
  • template project in C++

LESSON 2

Prerequisites

  • variables, basic data types
  • numeric, logic, and bitwise operators
  • bacis loops
  • standard input/output with defined format

 

Topics and Tasks

  • Practise the above mentioned items
  • try to implement the same output as you can see HERE with the usage of printf and cout; think about the differences
  • read some numeric data from the standard input
  • write a variable of unsigned int data type to the standard output in a binary form
  • create a new method that will print a given number in its binary form
  • ask the user for a number, read it and print it in the normal, binary and hexadecimal form

LESSON 3

Prerequisites

  • loops in C++
  • functions/methods ... basic notations, return values, etc.
  • arrays

 

Topics and Tasks

  • make a static declaration of an array of ten elements and initialize such array to following values {5, 7, 8, 6, 20, 100, 15, 13, 4, 5}
  • create a function that returns the largest element of the array (use FOR loop)
  • create a function that returns an index of the largest element of the array (use WHILE loop)
  • create a function that returns an index of a given number (use DO-WHILE loop)
  • create a function that returns a sum of two smallest elements of the array
  • create a method that prints all odd and then all even numbers
  • create a function that returns a number with more occurrences

 

Click HERE to download an illustrative solution.

Lesson 4

Prerequisites

  • functions
  • standard math library

 

Topics and Tasks

  • a short recap of the previous tasks
  • write a function f(x) that returns a single value for every x from the interval <-1000,1000>, if (x mod 3 == 0). The function is given by the following formula:

Math formula

  • think about the optimization. Do you really need the division and modulo? What about the absolute value?
  • try to modify the function such that the user can set the interval (upper and lower bound).

 

Click HERE to download an illustrative solution.

Lesson 5

Prerequisites

  • arrays, multi-dimensional arrays
  • functions

 

Topics and Tasks

  • create two vectors of a given dimension and fill them with random values from the interval <0,1>
  • write a function that returns a dot product of two vectors
  • let consider the first vector to be a column vector (a matrix of dimension [Mx1]) and create a function that multiplies this column vector with a row vector (a matrix of dimension [1xM]).

Lesson 6

Prerequisites

  • arrays, multi-dimensional arrays
  • functions

 

Topics and Tasks

  • prepare some global constants outside any method that will represent the dimensions of matrices, such that m = 10, n=20, k=30
  • create a matrix M1 of dimension m*k and a second matrix M2 of dimension k*n
  • fill matrices with random numbers
  • create a function that multiplies two matrices (M3 = M1 * M2)
  • create a function that creates a transposed matrix of the matrix M1
  • create a function that returns an upper triangular part of the matrix M1

Lesson 6 - 2nd part

Prerequisites

  • arrays, multi-dimensional arrays as the function arguments 

 

Topics and Tasks

  • a recap. of the previous lessos

 

Click HERE to download an illustrative example that shows different ways how to pass a 2D array to a function.

LESSON 7

Prerequisites

  • recursion

 

Topics and Tasks

  • create a non-recursive function to compute factorial of a given number
  • create a recursive function to compute factorial of a given number
  • create a non-recursive function that returns N-th number of the Fibonacci sequence 
  • create a recursive function that returns N-th number of the Fibonacci sequence 
  • optional task:
    • create a recursive function that search for an given element in the binary tree stored in an 1D array.

Lesson 8

Prerequisites

  • arrays, multi-dimensional arrays
  • functions
  • file streams

 

Topics and Tasks

  • create a matrix with a given dimension NxN
  • create a function that will fill the matrix with random boolean values
  • write into a text file the coordinates of all cells that satisfy all the following conditions:
  1. The upper neighbor is TRUE
  2. The left neighbor is FALSE
  3. The right neighbor is FALSE iff (= if and only if) the bottom neighbor is TRUE, or vice versa.
  • read the text file and create a new matrix M such that the read elements from the file will be represented by asterisk (*) in the matrix M.

Lesson 9

Prerequisites

  • arrays
  • functions
  • file streams
  • binary search

 

Topics and Tasks

  • create a text file
  • write into the file an array X of 1000 numbers such that X[i] < X[i+1]. Then close the file.
  • read the array from the file into a dynamic array
  • create a method that search for a given number in the array

LESSON 10 B

Prerequisites

  • file streams
  • bucket sort

 

Topics and Tasks

  • see the DATA FILE that contains a short part of the human genome (DNA) infected by an alien DNA :-) . This sequence is represented by a single line of chars: A (Adenine), G (Guanine), T (Thymine), and C (Cytosine), and the other letters are not parts of the human genome
  • the sequence has 4 bases (A,G,T,C). Count all occurrences of every single base
  • find the alien parts (characters) in the DNA. Return the characters and then indices as well
  • write a function that will return an index of the position of a given substring, e.g. AGCTAAAG

 

LESSON 11

Prerequisites

  • sorting

 

Topics and Tasks

  • see the TEMPLATE SOURCE FILE that contains read/write methods
  • generate a sequence of 10M floating point numbers and write it into a binary file.
  • read the file again and sort the numbers

 

Test 5

Zdrojová data

  • Stáhněte si následující datový soubor ... ZDE

 

Zadání

  • V souboru naleznete pouze znaky a číslice, nejsou tam žádné úmyslné chyby.
  • Napište metodu, která vypíše všechna písmena abecedy (a-z bez diakritiky), která se v souboru nenacházení. Pakliže žádná taková písmena neexistují, vypíše metoda: "Nenalezeno".