Preliminary activities: 1. Test your Java knowledge at www.adapt2.sis.pitt.edu/kt Your username and passwords have been distributed by now 2. Let's take a look at C++ programming in the attached pdf document on C++ introductory notes. or specifically the following topics: a. Basics of C++: ·
Structure of a
program ·
Variables.
Data Types. ·
Constants ·
Operators b. Basic Input/Outputc. Control Structuresd. Compound Data Types: ·
Arrays ·
Character
Sequences ·
Pointers ·
Dynamic Memory Introductionan algorithm is a procedure (a finite set of well-defined instructions) for accomplishing some task which, given an initial state, will terminate in a defined end-state. Download and read the attached document (introduction to algorithm.pdf) below to understand better, the concept of AlgorithmAnalysis of AlgorithmsThe computational complexity and efficient implementation of the algorithm are important in computing, and this depends on suitable data structures.In Computer Science, it is important to measure the quality of algorithms, especially the specific amount of a certain resource an algorithm needs. Examples of such resources would be time or memory storage. Nowadays, memory storage is almost a non-essential factor when designing algorithms but be aware that several systems still have memory constraints, such as Digital Signal Processors in embedded systems. Different algorithms may complete the same task with a different set of instructions in less or more time, space or effort than other. The analysis and study of algorithms is a discipline in Computer Science which has a strong mathematical background. It often relies on theoretical analysis of pseudo-code. To compare the efficiency of algorithms, we don't rely on abstract measures such as the time difference in running speed, since it too heavily relies on the processor power and other tasks running in parallel. The most common way of qualifying an algorithm is the Asymptotic Notation, also called Big O.
worst-case scenario, and can be used to describe the execution time required or the space used (e.g. in memory or on disk) by an algorithm.`for` loop and the function would return early, but Big O notation will always assume the upper limit where the algorithm will perform the maximum number of iterations.^{2})^{2}) represents an algorithm whose performance is directly proportional to the square of the size of the input data set. This is common with algorithms that involve nested iterations over the data set. Deeper nested iterations will result in O(N^{3}), O(N^{4}) etc.^{N})^{N}) denotes an algorithm whose growth will double with each additional element in the input data set. The execution time of an O(2^{N}) function will quickly become very large.O(log N). The iterative halving of data sets described in the binary search example produces a growth curve that peaks at the beginning and slowly flattens out as the size of the data sets increase e.g. an input data set containing 10 items takes one second to complete, a data set containing 100 items takes two seconds, and a data set containing 1000 items will take three seconds. Doubling the size of the input data set has little effect on its growth as after a single iteration of the algorithm the data set will be halved and therefore on a par with an input data set half the size. This makes algorithms like binary search extremely efficient when dealing with large data sets. For a more in-depth explanation, click on this link |