Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 2015-1Algorithms and Complexity15-2Time Complexity of Algorithms•The Time Complexity of an Algorithm is a measure of how the amount of “time” required to execute an algorithm grows as a function (in relation to) the problem size.problem sizeexecution timeproblem sizeexecution time15-3Time complexity Classes Exponential•Exponential Time Complexity:–The algorithm takes an amount of time to execute that grows much, much, faster than the size of the problem.•e.g., when the problem size is 10 times the original size, the time taken is 1000 times more!–This class of algorithms is impractical for large problem sizes •Examples include 2^n, 10^n, n^n, etc.problem sizeexecution time15-4Time complexity Classes Exponential•Just how fast does an exponential function grow?–How much would you save in one month if every day you deposit into your savings account an amount equal to what is already there on that day, starting with 1 cent on day one?1 + 1 + 2 + 4 + 8 + 16 + 32 + 64 + … cents15-5Time complexity Classes Exponential•Just how fast does an exponential function grow?–How much would you save in one month if every day you deposit into your savings account an amount equal to what is already there on that day, starting with 1 cent on day one? $10,737,418.24This is called an exponential explosion15-6Time complexity Classes Exponential•Algorithms with exponential time complexity often require the search for a solution in an “exponentially large” solution space.–Travelling Salesman Problem–Chess and other similar strategy games–For such problems we look for a “good enough” approximation to the solution. Typically, this works, but . . .•For some problems finding a good approximation is itself impractical (e.g., may take an exponential amount of time!)15-7Operating Systems15-8“Improving” the computer•Consider our view of the computer at this point:–Our resources (memory, CPU, I/O) are controlled by programs (really just one program)•Our computer is programmable, but how are we getting these programs into our computer? How will they run? Run one, reboot, repeat?•we don't even know how a single program is loaded and run...–what about more than one program?–the Von Neumann bottleneck only lets us run “one program” at a time•there would be a lot of issues in running multiple programs simultaneously•sharing devices, if possible, would be dangerous!–communicating with all the peripheral devices will require a lot of program code for each device–that’s a lot of devices to write program code for–And we haven’t talked about how humans will use the computer.•Enter the Operating System15-9What is an operating system?•What does an operating system do?–Control how programs are run on the computer–Provide an abstraction of the specific details of the hardware of the computer–That abstraction provides more than just the hardware itself•Provide a mechanism for hardware components to be shared among different programs–Including the CPU!–Provide the user an interface to the programs and files on the computer•The operating system (OS): –Collection of programs that form a “virtual hardware” –The OS is the foundation for other programs•All programs run on-top of the operating system rather than the real hardware•The OS is (essentially) the first program to run when you turn on the computer15-10What is an operating system?•What does an operating system do?•Programs (even the OS) run from memory•Remember that RAM is empty when we first turn on our computer–How does the OS get into memory to run in our computer?Real Physical Hardware CPU/Memory/Input/Output/Storage/PeripheralsOperating Systemprograms that provide an interface to the hardwaresome programrun by the OS onthe real hardwareon your behalfsoftwarehardware15-11What really runs first?•Remember ROM?–Small non-volatile “memory” that will be there when we turn on the computer–We place a small “hand-off” program into ROM and it will be run first when we turn on the computer•BIOS (Basic Input Output System)–Small “unchangeable” software stored in ROM–BIOS software is embedded (built into) in the motherboard»BIOS can be changed:»Flash update – it’s just rarely done–BIOS: •A collection of programs that have the capability of communicating with peripheral devices (hardware)–Keyboards, Disk drives, printers, display/monitors, and other devices.•BIOS is what let's us run our operating system15-12Booting the Computer•Booting (Starting) the computer:–The computer invokes the BIOS initialization program found in ROM•Makes the computer recognize the keyboard, floppy and the hard disk drives.–1. Diagnostics are run on the hardware devices in the computer–2. The program in ROM instructs the computer to look for an operating system •depending on your settings, the computer will look in different places at different orders – usually:–1st try the Floppy disk–Then try a CD-ROM–Then a hard disk (sometimes there are multiple hard disks)–3. The operating system (wherever found) must be loaded into RAM so it can run15-13Booting the Computer•Cold boot:–Starting up the computer by turning the power on (power was off previously).–BIOS is loaded into RAM and BIOS looks for and loads the operating system into RAM.•Warm boot:–Kick back to BIOS and reload the operating system into RAM without disrupting the power to the disk drives or power supply.–(aka reboot/restart)–both reload the operating system–the operating system is a collection of programs . . .15-14The composition of the OS•The Operating System is a collection of programs that provide essential services for the computer–The most important of these programs is known as the kernel–The kernel is the one program that controls (can invoke) all other programs in the Operating System•The kernel is what makes the services of the Operating System available.•when control of the computer is passed from BIOS to the Operating System, it’s really passed to the kernel program, which starts running.•Yet, the kernel is invisible to the user.15-15What you see of the OS•User Interface (UI): a program that acts as an interface between the Operating System and the user–(Provided by the