Tenta Flashcards
Hur många jämförelser behövs i värsta fall respektive bästa fall för hitta ett element i en sorterad lista med 16 element om du använder dig av binärsökning.
Motivera kortfattat ditt svar
I bästa fall (om man har tur behövs bara en jämförelse). I värsta fall kommer det behövas 𝑙𝑜𝑔(2 nere)16 + 1 jämförelser. I binärsökning kan man I varje iteration bortse från hälften av återstående element. Efter 𝑙𝑜𝑔(2 nere )16 delningar på mitten har man endast 1 element kvar. Om man inte redan hittat elementet man söker efter behövs ytterligare 1 jämförelse.
Stämmer det att en rutin (algoritm) för att lösa ett 𝒩𝒫-fullständigt problem kan användas som subrutin för att läsa vilket problem som helst i 𝒫?
Motivera ditt svar. (2p)
Ja, eftersom en rutin för att lösa ett 𝒩𝒫 fullständigt problem kan användas som subrutin för att läsa vilket problem som helst i 𝒩𝒫 och 𝒫 är en delmängd av 𝒩𝒫
include <stdio.h></stdio.h>
Look at the following C code, what will be printed after it is executed? Motivate why the output is the one you think is. (2pt)
int addOne(int var)
{
var = var + 1;
}
int main()
{
int a = 10;
addOne(a);
addOne(a);
addOne(a);
printf(“%d “, a);
return 0;
}
The output is 10, this is because the function does change the value of a, because arguments are passed as value to functions in C, that is, their value is copied locally in the function, without modifying the variable outside the function.
include <stdio.h></stdio.h>
We change the code a little, what would be printed now? Please motivate the answer. (2 pt)
int addOne(int* var)
{
*var = *var + 1;
}
int main()
{
int a = 10;
addOne(&a);
addOne(&a);
addOne(&a);
printf(“%d “, a);
return 0;
}
In the second case the output is 13 because we pass the address of a, then the value inside the memory position is modified which survives after the execution of the function.
Full in the first column of this table placing the following different types of memory:
DRAM, EEPROM, SRAM, PROM, NVRAM, Masked ROM, Flash, EPROM
The memory types are placed in this order: SRAM, DRAM, Masked ROM, PROM, EPROM, EEPROM, Flash, NVRAM
Explain the difference between “Memory mapped I/O” and “Port mapped I/O”
Memory mapped I/O is mapped into the same address space as program memory and/or user memory, and is accessed in the same way. Memory and IO share the same address and are used in the same way.
Port mapped I/O uses a separate, dedicated address space and is accessed via a dedicated set of microprocessor instructions. IO and memory use different address spaces, when accessing memory, the programmer must specify if it’s memory or IO
You are developing the firmware for a microntroller that controls the lights of a Christmas tree.
One of the pins of the microcontroller is connected to a button, which is used to control the device. The button is connected, on one side, to the microcontroller and on the other side to the voltage supply (Vcc).
A) (2 pt)
How should you configure your pin to detect when the button is pressed? You have the following 2 options to configure:
* Direction: can be input or output
* Connection: can be direct, pulldown or pullup.
B) (2 pt)
You want your lights to fade and blink smoothly, so you program the microcontroller to emit Pulse Width Modulation (PWM) pulses on a pin to control the light intensity. The PWM pulses are controlled by a timer, which, you estimate, should tick at 1KHz so that users would not notice any flickering. Your microcontroller has a master clock of 8MHz, a prescale register of 8 bits and a compare register of 8 bits. How do you set the values for these two in order to obtain the desired frequency of 1KHz?
A)
Input and pulldown. Pulldown is needed because when the button is not pressed, the pin is floating.
B)
Both the prescaler, P, and the compare register, C, accept values between 1 and 256.
Your target is 8M / (P x C) = 1000
Which means that P x C = 8000
We can set, for example, P = 200 -> C = 8000/200 = 40
Vilka steg behövs för att ta bort första element i en dubbel-länkad lista?(2pt)
Antag att det finns minst 2 element i listan.
1. Spara undan adressen till första elementet i en temp-variabel (så att man inte tappar bort det). Dvs temp = start
2. Peka om listans start-pekare (dvs den pekare som pekar på listans första element), så att den istället pekar på listans andra element. Dvs start = temp->next, eller start = start->next
3. Låt listans andra elements prev-pekare peka på null. Dvs start->prev = null (eller temp- >next->prev = null
4. Avallokera minnet för det element som tagits bort. Dvs det element som ligger i temp-variabeln
Vid sortering av en lista är basoperation att jämföra två element.
a. Vad har algoritmen bubble sort för tidskomplexitet? Använd 𝜃-notation. (1pt)
b. Hur många basoperationer behövs (alltid) för att sortera en lista med 10 element med hjälp av bubble sort? (1pt)
a. Bubble sort har tidskomplexiteten 𝜃(𝑛2).
b. Det behövs 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 𝑛∙(𝑛−1)/ 2 = 45 jämförelser (basoperationer)
Är följande binära sökträd balanserat? Motivera kortfattat ditt svar. (1pt) (20231108 fråga 5)
Trädet är inte balanserat. Vänster subträd till noden med värdet 9 har höjden 2, medans höger subträd till samma nod har höjden 0.
Lägg in en nod med värde 10 i sökträdet i trädet ovan, och visa hur trädet ser ut efteråt. Är trädet balanserat? Motivera kortfattat ditt svar.(2pt) (20231108 fråga 5)
Trädet är balanserat då höjden på vänster och höger subträd inte skiljer sig med mer än 1 för någon nod i trädet
What is the size of an integer in C?
How can I choose a specific size (for example 8 bits) for an integer?
The size of an integer depends on the environment, including compiler, CPU architecture and used libraries.
In C99 you can import inttypes.h and use specific defines for specific sizes (fixed-width integer types)
Describe the steps needed to compile a piece of code from source code to executable, in C
- Preprocessing: performs simple text modification.
- Compilation: generates assembler code from source code.
- Assembly: generates machine instructions from assembler code.
- Linking: links all “modules” together into one executable.
A peripheral is connected to a microcontroller using the I2C protocol. In order to activate the peripheral, the microcontroller needs to write the content of a register, the address of which is specified in one byte (for example 00101010), with a specific 1 byte content (for example 10011001). The I2C address of the peripheral is 00110011.
With the help of the pictures below, describe the sequence of bits sent by the microcontroller to the peripheral (20231108 fråga 8)
The microcontroller sends:
- Start signal (SDA->low SCL->high)
- Address of the peripheral (00110011)
- Write bit
- ACK by receiver
- Register address (00101010)
- ACK by receiver
- Value (10011001)
- ACK by receiver
- Stop signal (SDA->high SCL->high)
What are the advantages and disadvantages of using “Direct conversion” versus “Successive approximation” in Digital to Anaologue Conversion.
Direct conversion is almost instantaneous but requires an exponentially higher number of comparators in relation to the number of bits, making the circuit more expensive. Successive approximation, on the other hand, requires linearly higher time for number of bits used, the circuit is smaller but slower
List the 5 views of the 4+1 view model.
Just listing the names correctly is enough for 1 point.
- The logical view. It shows the key abstractions in the system as objects or object classes “code structure”. It focuses on the functionality.
- The process view shows how, at run-time, the system is composed of interacting processes
“running code”. It focuses on concurrency and distribution. - The implementation/development view shows how the software is decomposed for
development “who does what”. It focuses on the on the software development
environment. - The physical/deployment view shows the system hardware and how software processes are
distributed across the processors in the system “things you can touch”. - All views are related using use cases or scenarios. This view shows how the elements in the
four views work together in relation to how they are used externally, from people or
machines.
